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