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