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

Вам потрібно створити структуру даних, яка являє собою масив цілих чисел. Спочатку масив порожній. Вам потрібно підтримувати дві операції:

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

Звичайно ж, ця структура повинна бути достатньо хорошою.

Вхідні дані

Перший рядок містить кількість операцій n (1 ≤ n ≤ 200000) над масивом. Наступні n рядків описують самі операції. Усі операції додавання є коректними. Усі числа, що зберігаються у масиві, за модулем не перевищують 109.

Вихідні дані

Для кожної операції ? у окремому рядку виведіть її результат.