题目描述

给定一个数组 $A=(a_1,a_2,⋯ ,a_n)$, 请对该数组执行 $m$ 次修改或查询操作: 若操作为 1 x y, 表示将 $a_x$ 的值修改为 $y$;

若操作为 2 l r p 表示求 $a_p$ 在 $a_l,a_{l+1},⋯ ,a_r$ 中是第几小的（比 $a_p$ 小的元素个数加 $1$)。

输入描述

输入的第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,⋯ ,a_n$, 表示数组中每个数的初始值, 相邻的 整数之间用一个空格分隔。

第三行包含一个整数 $m$。

接下来 $m$ 行每行包含一个操作, 可能是 1 x y 或 2 l r p​, 相邻的整数之间用一个空格分隔。

输出描述

输出一行, 包含多个整数, 相邻的整数之间用一个空格分隔, 依次表示第 二种操作的答案。

3
1 2 3
3
2 1 3 2
1 2 4
2 1 3 2

2 3

评测用例规模与约定：

对于 20% 的评测用例, $n≤500$；

对于 40% 的评测用例， $n≤5000$;

对于所有评测用例, $1≤n≤100000，1≤m≤2n，1≤a_i,y_i≤10^6， 1≤x_i≤n，1≤l_i≤p_i≤r_i≤n$∘