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

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

• запрос: "**? i j**" - возвращает минимальный элемент между i-ым и j-ым включительно;
• изменение: "**+ i x**" - добавить элемент x после i-го элемента списка. Если i = 0, то элемент добавляется в начало массива.

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

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

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

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

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