该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

插入排序是一种常见且简单的排序算法。假设数组 $a$ 的下标从 $1$ 开始，一种插入排序写法如下：依次枚举 $i=1,2,\ldots,n$；对于每个 $i$，从 $j=i$ 开始递减到 $2$，若 $a_j<a_{j-1}$，就交换 $a_j$ 与 $a_{j-1}$。

现在给定一个长度为 $n$ 的数组 $a$，需要支持 $Q$ 次操作：

• 1 x v：将 $a_x$ 修改为 $v$。修改会保留并影响之后的操作。
• 2 x：假设对当前数组执行上面的插入排序，询问原数组中 $a_x$（即当前第 $x$ 个元素）排序后所处的位置。此操作不改变数组，也不会保留排序结果。

所有操作中，类型 1 的操作次数不超过 $5000$。

输入格式

从 sort.in 读入。第一行包含两个正整数 $n,Q$，分别表示数组长度和操作次数。第二行包含 $n$ 个空格分隔的非负整数，表示初始数组。接下来 $Q$ 行，每行表示一次操作：类型 1 的操作有三个正整数 1 x v，类型 2 的操作有两个正整数 2 x。

输出格式

向 sort.out 输出。对于每一次类型 2 的询问，输出一行一个正整数，表示对应元素排序后的位置。

样例

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

1
1
2

样例说明

修改前，三个元素在插入排序后的位置分别为 3、2、1。将第 3 个元素改为 2 后，当前位置的数组为 $(3,2,2)$，三个元素排序后的位置分别为 3、1、2。

虽然第 2、3 个元素的值相同，但它们仍是不同元素；排序时相等元素不会交换，因此第 2 个元素排在第 3 个元素之前。

数据范围与特殊性质

所有数据满足 $1\le n\le8000$，$1\le Q\le2\times10^5$，$1\le x\le n$，$1\le v,a_i\le10^9$。所有操作中类型 1 的操作次数不超过 $5000$。

测试点 $1\sim4$：$n\le10,Q\le10$；$5\sim9$：$n\le300,Q\le300$；$10\sim13$：$n\le1500,Q\le1500$；$14\sim16$：$n\le8000,Q\le8000$，且所有输入的 $a_i$、$v$ 互不相同；$17\sim19$：$n\le8000,Q\le8000$；$20\sim22$：$n\le8000,Q\le2\times10^5$，且所有输入的 $a_i$、$v$ 互不相同；$23\sim25$：$n\le8000,Q\le2\times10^5$。