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

2021 T2 插入排序

主知识点：排序与计数。交叉标签：排序、模拟、数据结构。
暴力标注：不属于重点 DP 退路题。
OJ 使用标准输入与标准输出。原比赛文件名为 sort.in / sort.out；下方如保留原文件约定，以本句的 OJ 约定为准。
时限 1 秒；内存 512 MiB；测试点 25；总分 100。
数据来源：公开存档数据；未逐文件对照官网下载包。

题目描述

维护长度为 $n$ 的非负整数数组，下标从 1 开始。两类操作为：

• 1 x v：把原数组第 $x$ 个元素永久修改为 $v$；
• 2 x：询问将当前数组按稳定的升序插入排序后，原下标 $x$ 的元素所在位置。仅询问，排序结果不保留。

稳定排序只在左元素严格大于右元素时交换；相等元素保持原数组下标顺序。第一类操作不超过 5000 次。

输入格式

第一行，包含两个正整数 $n, Q$，表示数组长度和操作次数。

第二行，包含 $n$ 个空格分隔的非负整数，其中第 $i$ 个非负整数表示 $a_i$。

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

输出格式

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

样例

样例 1

输入：

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

输出：

1
1
2

数据范围与特殊性质

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

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

各测试点的附加限制及分值如下表所示。

附加样例

本题的公开样例整理在对应的“样例”ZIP 中。样例不计入评测测试点；题面中的样例也已保留。

来源与整理说明

题目原作者/发布者：中国计算机学会 CCF / NOI。题意经过改写，保留公式、输入输出、样例及约束；知识点和暴力标注为本次整理补充。

• 题面及约束校对来源：洛谷 CCF_NOI 题目 P7910
• 赛事：CSP-J 第二轮入门级 2021。
• 详细数据来源、版本和哈希见总包 来源与校验/manifest.json。