Мінімальне інтервальне значення
Компанія Giggle відкриває свій новий офіс у Судиславлі, і ви запрошені на співьесіду. Ваша задача - розв'язати поставлену задачу.
Вам потрібно створити структуру даних, яка являє собою масив цілих чисел. Спочатку масив порожній. Вам потрібно підтримувати дві операції:
запит: "? i j" - повертає мінімальний елемент між i-им та j-им, включно;
зміна: "+ i x" - додати елемент x після i-го елементу списку. Якщо i = 0, то елемент додається у початок масиву.
Звичайно ж, ця структура повинна бути достатньо хорошою.
Вхідні дані
Перший рядок містить кількість операцій n (1 ≤ n ≤ 200000) над масивом. Наступні n рядків описують самі операції. Усі операції додавання є коректними. Усі числа, що зберігаються у масиві, за модулем не перевищують 10^9.
Вихідні дані
Для кожної операції ? у окремому рядку виведіть її результат.