Вы играли со своей перестановкой \(p\) длины \(n\), но потеряли ее в Блэр, штат Алабама!
К счастью, вы помните некоторую информацию о перестановке. А точнее, вы помните массив \(b\) длины \(n\), где \(b_i\) — это количество индексов \(j\) таких, что \(j < i\) и \(p_j > p_i\).
У вас есть массив \(b\), и вы хотите восстановить перестановку \(p\). Однако ваша память не идеальна, и вы постоянно меняете значения массива \(b\), как вспоминаете что-то еще. В следующие \(q\) секунд каждую секунду происходит одно из следующего:
- \(1\) \(i\) \(x\) — вы вспоминаете, что \(b_i\) равно \(x\);
- \(2\) \(i\) — вам нужно определить значение элемента \(p_i\). Если существует более одного ответа, выведите любой. Можно доказать, что при данных ограничениях всегда найдется хотя бы одна перестановка.
Отвечайте на запросы, и вы сможете вспомнить массив!
Выходные данные
На каждый запрос вида \(2\) выведите одно число — ответ на заданный запрос.
Примечание
В первом примере первоначально есть ровно одна перестановка, удовлетворяющая условиям: \([1, 2, 3]\), так как должна содержать \(0\) инверсий.
После запроса вида \(1\) массив \(b\) становится равен \([0, 1, 0]\). Единственная перестановка \(p\), порождающая данный массив — это \([2, 1, 3]\). В этой перестановке \(b_2\) равен \(1\), так как \(p_1 > p_2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
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
|