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