D. Инвертируем инверсии
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы играли со своей перестановкой $$$p$$$ длины $$$n$$$, но потеряли ее в Блэр, штат Алабама!

К счастью, вы помните некоторую информацию о перестановке. А точнее, вы помните массив $$$b$$$ длины $$$n$$$, где $$$b_i$$$ — это количество индексов $$$j$$$ таких, что $$$j < i$$$ и $$$p_j > p_i$$$.

У вас есть массив $$$b$$$, и вы хотите восстановить перестановку $$$p$$$. Однако ваша память не идеальна, и вы постоянно меняете значения массива $$$b$$$, как вспоминаете что-то еще. В следующие $$$q$$$ секунд каждую секунду происходит одно из следующего:

  1. $$$1$$$ $$$i$$$ $$$x$$$ — вы вспоминаете, что $$$b_i$$$ равно $$$x$$$;
  2. $$$2$$$ $$$i$$$ — вам нужно определить значение элемента $$$p_i$$$. Если существует более одного ответа, выведите любой. Можно доказать, что при данных ограничениях всегда найдется хотя бы одна перестановка.

Отвечайте на запросы, и вы сможете вспомнить массив!

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

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

Во второй строке заданы $$$n$$$ целых чисел $$$b_1, b_2 \ldots, b_n$$$ ($$$0 \leq b_i < i$$$) — то, как вы помнили массив $$$b$$$ сначала.

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

В следующих $$$q$$$ строках заданы сами запросы, каждый одного из следующих видов:

  • $$$1$$$ $$$i$$$ $$$x$$$ ($$$0 \leq x < i \leq n$$$) описывает запрос вида $$$1$$$;
  • $$$2$$$ $$$i$$$ ($$$1 \leq i \leq n$$$), описывает запрос вида $$$2$$$.

Гарантируется, что есть хотя бы один запрос вида $$$2$$$.

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

На каждый запрос вида $$$2$$$ выведите одно число — ответ на заданный запрос.

Примеры
Входные данные
3
0 0 0
7
2 1
2 2
2 3
1 2 1
2 1
2 2
2 3
Выходные данные
1
2
3
2
1
3
Входные данные
5
0 1 2 3 4
15
2 1
2 2
1 2 1
2 2
2 3
2 5
1 3 0
1 4 0
2 3
2 4
2 5
1 4 1
2 3
2 4
2 5
Выходные данные
5
4
4
3
1
4
5
1
5
4
1
Примечание

В первом примере первоначально есть ровно одна перестановка, удовлетворяющая условиям: $$$[1, 2, 3]$$$, так как должна содержать $$$0$$$ инверсий.

После запроса вида $$$1$$$ массив $$$b$$$ становится равен $$$[0, 1, 0]$$$. Единственная перестановка $$$p$$$, порождающая данный массив — это $$$[2, 1, 3]$$$. В этой перестановке $$$b_2$$$ равен $$$1$$$, так как $$$p_1 > p_2$$$.