eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Минимальное интервальное значение

Минимальное интервальное значение

Лимит времени 2 секунды
Лимит использования памяти 128 MiB

Компания Giggle открывает свой новый офис в Судиславле, и Вы приглашены на собеседование. Ваша задача - решить поставленную задачу.

Вам нужно создать структуру данных, которая представляет собой массив целых чисел. Изначально массив пуст. Вам нужно поддерживать две операции:

  • запрос: "? i j" - возвращает минимальный элемент между i-ым и j-ым включительно;

  • изменение: "+ i x" - добавить элемент x после i-го элемента списка. Если i = 0, то элемент добавляется в начало массива.

Конечно, эта структура должна быть достаточно хорошей.

Входные данные

Первая строка содержит количество операций n (1n200000) над массивом. Следующие n строк описывают сами операции. Все операции добавления являются корректными. Все числа, хранящиеся в массиве, по модулю не превосходят 10^9.

Выходные данные

Для каждой операции ? в отдельной строке выведите её результат.

Пример

Входные данные #1
8
+ 0 5
+ 1 3
+ 1 4
? 1 2
+ 0 2
? 2 4
+ 4 1
? 3 5
Выходные данные #1
4
3
1