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