你正在玩长度 $$$n$$$ 的排列 $$$p$$$,但你在阿拉巴马州布莱尔输了!
幸运的是,您还记得一些有关排列的信息。更具体地说,您记得一个长度为 $$$n$$$ 的数组 $$$b$$$,其中 $$$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$$$ 类型的每个查询,打印一个整数 - 查询的答案。
示例
输入 #1
3 0 0 0 7 2 1 2 2 2 3 1 2 1 2 1 2 2 2 3
输出 #1
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
输出 #2
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$$$。