题目描述

有以下排序算法，可将数组 $a$ 中的元素从小到大排序：

for (int i = 1; i <= n; i++) {
	for (int j = i; j >= 2; j--) {
		if (a[j] < a[j-1]) {
			int t = a[j-1];
			a[j-1] = a[j];
			a[j] = t;
		}
	}
}

现有一长度为 $n$ 的数组 $a$，编号从 $1$ 开始，数组中的元素均为 int 范围内自然数。

对数组做如下 $m$ 次操作：

• 操作$1$：输入1 i x，将 $a$ 的第 $i$ 个元素，即 a[i] 的值，修改为 $x$。数据保证 $1 \le i \le n$，$1 \le x \le 10^9$。注意：该操作修改的值会保留，即会影响后续的操作。
• 操作$2$：输入2 i，将 数组 $a$ 按照上面的代码进行排序，然后输出原数组 $a$ 的第 $i$ 个元素，即 a[i] 在排序后的新数组中的下标。数据保证 $1 \le i \le n$。注意：该操作不会修改原数组，排序后的数组不会被保留，即不影响后续的操作。

数据保证操作 $1$ 的次数不超过 $5000$。

输入格式

第一行，为两个正整数 $n, m$，即数组长度与操作次数。

第二行，为 $n$ 个自然数，即原数组 $a$ 的元素，空格隔开

接下来 $m$ 行，每行 $2$ 至 $3$ 个正整数，表示一次操作。

输出格式

针对每次个操作 $2$ 的询问，输出一行答案。

样例 #1

样例输入 #1

3 5
3 2 1
2 3
1 3 2
2 2
1 2 3
2 2

样例输出 #1

1
1
3

提示

【数据范围】

对于所有测试数据，满足 $1 \le n \le 8000$，$1 \le m \le 2 \times {10}^5$，$1 \le i \le n$，$1 \le x,a_i \le 10^9$。

对于所有测试数据，保证最多有 $5000$ 次操作$1$。