E. Запросы на массиве
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Абитуриент Максим усиленно готовится к поступлению в МИСИС по олимпиаде. Поэтому он попросил своего учителя дать ему задачу для тренировки. Учитель знает, что Максим испытывает трудности с задачами, в которых нужно отвечать на запросы, поэтому дал ему именно такую задачу.

Максиму было тяжело, но он справился с этой задачей. Теперь Максим предлагает вам решить эту задачу, потому что она ему показалась очень интересной.

В этой задаче вам дан массив, состоящий из $$$n$$$ целых чисел.

Требуется обработать $$$q$$$ запросов двух типов. Каждый запрос состоит из двух целых чисел — типа запроса и номера элемента массива:

  • $$$1$$$ $$$i$$$ — в ответ на запрос первого типа необходимо вывести значение наименьшего элемента $$$a_j$$$ такого, что $$$a_j \gt a_i$$$ и $$$j \gt i$$$.
  • $$$2$$$ $$$i$$$ — после запроса второго типа необходимо выполнить операцию изменения: $$$a_i = -a_i$$$.
Входные данные

В первой строке задано целое число $$$n$$$ $$$(2 \le n \le 10^5)$$$ — размер массива $$$a$$$.

Во второй строке через пробел заданы $$$n$$$ целых чисел — элементы массива $$$a$$$ $$$(-10^5 \le a_i \le 10^5$$$ для $$$1 \le i \le n - 1,\:a_n = 10^6)$$$.

В третьей строке задано целое число $$$q$$$ $$$(1 \le q \le 10^5)$$$ — количество запросов.

Каждая строка из следующих $$$q$$$ содержит два целых числа $$$t$$$ и $$$i$$$ $$$(1 \le t \le 2,\:1 \le i \le n - 1)$$$ — тип запроса и номер элемента массива соответственно.

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

На каждый запрос первого типа выведите в отдельной строке единственное целое число — ответ на этот запрос.

Пример
Входные данные
5
4 3 5 2 1000000
5
1 1
2 1
1 1
2 2
1 1
Выходные данные
5
2
-3