题目描述

在一个遥远的数字王国里，小Z是一位年轻的学徒，他正在学习一种古老的算法魔法——插入排序。H老师是这个领域的大师，他向小Z传授了插入排序的奥秘，并给了他一项挑战，以测试他对这种魔法的掌握程度。

数字王国的居民们都是一些数字精灵，它们居住在由n个房间组成的数组大厦中。每个精灵都有一个特定的能力值，这些能力值存储在数组大厦的房间中，从房间1到房间n。小Z的任务是支持Q次操作，这些操作将影响数字精灵的能力值和他们在数组大厦中的位置。 操作有两种类型：

1. ​能力值变更​："1 x v"，小Z需要将房间x中的数字精灵的能力值更改为v。这个操作会改变精灵的能力，并且这种改变会影响他们在数组大厦中的排名。
2. ​查询排名​："2 x"，小Z需要告诉H老师，如果按照插入排序的规则对数组大厦中的精灵进行排序，房间x中的数字精灵将位于哪个新房间。这个操作不会改变任何精灵的能力值，也不会影响他们在数组大厦中的当前位置。

H老师是一个不喜欢变化的大师，他保证能力值变更的操作不会超过5000次。小Z需要找到一种方法来高效地处理这些操作，并快速回答H老师的查询。

为了解决这个问题，小Z决定使用一种叫做映射魔法的技术。他创建了一个魔法映射，记录每个数字精灵当前所在的房间。每当进行能力值变更操作时，小Z会更新映射，确保每个精灵的能力值和他们的位置能够一一对应。

对于查询排名的操作，小Z使用了一种叫做排名追踪的魔法。他记录了一个排名列表，这个列表显示了如果按照插入排序的规则进行排序，每个精灵将会在哪个房间。当能力值变更时，小Z会更新这个排名列表，以反映新的排序情况。

通过这种方法，小Z能够快速地响应H老师的每一次操作，无论是变更能力值还是查询排名。最终，小Z不仅掌握了插入排序的魔法，还学会了如何高效地管理和查询数字精灵的能力值和位置，成为了数字王国中的一位出色的算法魔法师。

输入格式

输入的第一行包含两个正整数 n, Q，表示数组长度和操作次数。保证 1 ≤ n ≤8, 000, 1 ≤ Q ≤ 2 × 105。

输入的第二行包含 n 个空格分隔的非负整数，其中第 i 个非负整数表示 ai。保证1 ≤ ai ≤ 109。

接下来 Q 行，每行 2 ∼ 3 个正整数，表示一次操作，操作格式见题目描述。

输出格式

对于每一次类型为 2 的询问，输出一行一个正整数表示答案。

样例：

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

1
1
2

【样例 1 解释】

在修改操作之前，假设 H 老师进行了一次插入排序，则原序列的三个元素在排序结束后所处的位置分别是 3, 2, 1。

在修改操作之前，假设 H 老师进行了一次插入排序，则原序列的三个元素在排序结束后所处的位置分别是 3, 1, 2。

注意虽然此时 a2 = a3，但是我们不能将其视为相同的元素。 【数据范围】

对于所有测试数据，满足 1 ≤ n ≤ 8, 000, 1 ≤ Q ≤ 2×105, 1 ≤ x ≤ n, 1 ≤ v, ai ≤ 109。

对于所有测试数据，保证在所有 Q 次操作中，至多有 5000 次操作属于类型一。