6135: CSP-J2021 T2：插入排序（sort）
[Creator : ]
Description
插入排序是一种非常常见且简单的排序算法。小 Z 是一名大一的新生，今天 H 老师刚刚在上课的时候讲了插入排序算法。
假设比较两个元素的时间为 $\mathcal O(1)$，则插入排序可以以 $\mathcal O(n^2)$ 的时间复杂度完成长度为 $n$ 的数组的排序。不妨假设这 $n$ 个数字分别存储在 $a_1,\ a_2,\ \ldots,\ a_n$ 之中，则如下伪代码给出了插入排序算法的一种最简单的实现方式：
这下面是 C/C++ 的示范代码：
这下面是 Pascal 的示范代码：
H 老师给了一个长度为 $n$ 的数组 a，数组下标从 $1$ 开始，并且数组中的所有元素均为非负整数。小 Z 需要支持在数组 a 上的 $Q$ 次操作，操作共两种，参数分别如下：
$1\ x\ v$：这是第一种操作，会将 a 的第 $x$ 个元素，也就是 $a_x$ 的值，修改为 $v$。保证 $1 \le x \le n,\ 1 \le v \le 10^9$。注意这种操作会改变数组的元素，修改得到的数组会被保留，也会影响后续的操作。
$2\ x$：这是第二种操作，假设 H 老师按照上面的伪代码对 a 数组进行排序，你需要告诉 H 老师原来 a 的第 $x$ 个元素，也就是 $a_x$，在排序后的新数组所处的位置。保证 $1 \le x \le n$。注意这种操作不会改变数组的元素，排序后的数组不会被保留，也不会影响后续的操作。
H 老师不喜欢过多的修改，所以他保证类型 $1$ 的操作次数不超过 $5000$。
小 Z 没有学过计算机竞赛，因此小 Z 并不会做这道题。他找到了你来帮助他解决这个问题。
假设比较两个元素的时间为 $\mathcal O(1)$，则插入排序可以以 $\mathcal O(n^2)$ 的时间复杂度完成长度为 $n$ 的数组的排序。不妨假设这 $n$ 个数字分别存储在 $a_1,\ a_2,\ \ldots,\ a_n$ 之中，则如下伪代码给出了插入排序算法的一种最简单的实现方式：
这下面是 C/C++ 的示范代码：
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;
}
这下面是 Pascal 的示范代码：
for i:=1 to n do
for j:=i downto 2 do
if a[j]<a[j-1] then
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
end;
为了帮助小 Z 更好的理解插入排序，小 Z 的老师 H 老师留下了这么一道家庭作业： H 老师给了一个长度为 $n$ 的数组 a，数组下标从 $1$ 开始，并且数组中的所有元素均为非负整数。小 Z 需要支持在数组 a 上的 $Q$ 次操作，操作共两种，参数分别如下：
$1\ x\ v$：这是第一种操作，会将 a 的第 $x$ 个元素，也就是 $a_x$ 的值，修改为 $v$。保证 $1 \le x \le n,\ 1 \le v \le 10^9$。注意这种操作会改变数组的元素，修改得到的数组会被保留，也会影响后续的操作。
$2\ x$：这是第二种操作，假设 H 老师按照上面的伪代码对 a 数组进行排序，你需要告诉 H 老师原来 a 的第 $x$ 个元素，也就是 $a_x$，在排序后的新数组所处的位置。保证 $1 \le x \le n$。注意这种操作不会改变数组的元素，排序后的数组不会被保留，也不会影响后续的操作。
H 老师不喜欢过多的修改，所以他保证类型 $1$ 的操作次数不超过 $5000$。
小 Z 没有学过计算机竞赛，因此小 Z 并不会做这道题。他找到了你来帮助他解决这个问题。
Input
第一行，包含两个正整数 $n,\ Q$，表示数组长度和操作次数。
第二行，包含 $n$ 个空格分隔的非负整数，其中第 $i$ 个非负整数表示 $a_i$。
接下来 $Q$ 行，每行 $2 \sim 3$ 个正整数，表示一次操作，操作格式见【题目描述】。
第二行，包含 $n$ 个空格分隔的非负整数，其中第 $i$ 个非负整数表示 $a_i$。
接下来 $Q$ 行，每行 $2 \sim 3$ 个正整数，表示一次操作，操作格式见【题目描述】。
Output
对于每一次类型为 $2$ 的询问，输出一行一个正整数表示答案。
Constraints
对于所有测试数据，满足 $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$ 次操作属于类型一。
对于所有测试数据，保证在所有 $Q$ 次操作中，至多有 $5000$ 次操作属于类型一。
Sample 1 Input
3 4
3 2 1
2 3
1 3 2
2 2
2 3
Sample 1 Output
1
1
2
在修改操作之前，假设 H 老师进行了一次插入排序，则原序列的三个元素在排序结束后所处的位置分别是 $3,\ 2,\ 1$。
在修改操作之后，假设 H 老师进行了一次插入排序，则原序列的三个元素在排序结束后所处的位置分别是 $3,\ 1,\ 2$。
注意虽然此时 $a_2 = a_3$，但是我们不能将其视为相同的元素。
在修改操作之后，假设 H 老师进行了一次插入排序，则原序列的三个元素在排序结束后所处的位置分别是 $3,\ 1,\ 2$。
注意虽然此时 $a_2 = a_3$，但是我们不能将其视为相同的元素。
Sample 2 Input
10 10
877332633 234569527 229171089 600324455 1458624 887548760 574229391 234569527 202374341 849045846
2 7
1 2 234569527
1 4 600324455
2 6
2 9
2 6
2 3
1 5 246345024
1 6 856960762
2 7
Sample 2 Output
6
10
2
10
3
6
该测试点数据范围同测试点 $1 \sim 2$。
Sample 3 Input
300 300
1458624 234569527 296010479 234569527 121412483 92620085 246345024 234569527 574229391 800165334 856960762 405872753 121412483 298520436 52839209 1458624 679986156 405872753 629318818 405872753 298520436 856960762 92620085 1458624 574229391 172426594 457674832 121412483 121412483 46472898 121412483 933223793 679986156 800165334 296010479 856960762 234569527 172426594 800165334 457674832 629318818 246345024 405872753 121412483 52839209 405872753 174169584 457674832 298520436 1458624 800165334 121412483 234569527 296010479 679986156 629318818 174169584 172426594 298520436 856960762 457674832 1458624 1458624 46472898 856960762 298520436 933223793 856960762 629318818 202374341 46472898 933223793 405872753 246345024 121412483 52839209 234569527 629318818 234569527 457674832 856960762 679986156 246345024 246345024 457674832 298520436 296010479 298520436 296010479 246345024 296010479 174169584 800165334 405872753 298520436 405872753 574229391 298520436 933223793 574229391 174169584 856960762 405872753 202374341 629318818 574229391 92620085 202374341 800165334 234569527 405872753 574229391 298520436 121412483 172426594 174169584 234569527 174169584 52839209 46472898 800165334 234569527 92620085 46472898 574229391 629318818 46472898 856960762 92620085 234569527 298520436 933223793 574229391 856960762 1458624 800165334 46472898 574229391 121412483 679986156 246345024 246345024 172426594 298520436 174169584 172426594 234569527 172426594 234569527 298520436 246345024 933223793 629318818 172426594 52839209 172426594 296010479 202374341 174169584 52839209 298520436 46472898 172426594 629318818 296010479 52839209 246345024 121412483 298520436 933223793 574229391 174169584 246345024 298520436 121412483 298520436 246345024 629318818 174169584 234569527 46472898 202374341 405872753 679986156 1458624 234569527 234569527 296010479 856960762 92620085 92620085 52839209 121412483 629318818 1458624 296010479 92620085 405872753 246345024 202374341 856960762 172426594 856960762 92620085 457674832 52839209 405872753 1458624 856960762 405872753 405872753 172426594 405872753 46472898 92620085 457674832 92620085 172426594 202374341 933223793 296010479 298520436 246345024 121412483 933223793 629318818 246345024 202374341 296010479 234569527 933223793 296010479 679986156 234569527 298520436 629318818 1458624 174169584 629318818 629318818 121412483 405872753 172426594 574229391 202374341 296010479 405872753 296010479 296010479 933223793 202374341 52839209 172426594 800165334 92620085 46472898 202374341 202374341 629318818 92620085 298520436 174169584 298520436 298520436 172426594 679986156 234569527 457674832 800165334 52839209 234569527 92620085 933223793 46472898 234569527 457674832 52839209 298520436 246345024 202374341 856960762 629318818 574229391 234569527 856960762 46472898 52839209 856960762 457674832 234569527 172426594 800165334 92620085 202374341 933223793 172426594 574229391 933223793 234569527 92620085
2 184
1 220 172426594
1 167 296010479
2 94
1 128 52839209
1 266 800165334
1 179 1458624
2 140
1 158 52839209
2 194
1 193 234569527
2 277
1 229 172426594
2 165
1 156 92620085
2 192
2 247
2 18
2 177
2 284
1 133 856960762
2 266
1 297 1458624
2 273
1 157 234569527
2 132
1 234 246345024
2 149
1 198 46472898
2 221
1 275 121412483
2 149
1 6 574229391
2 210
1 209 574229391
2 290
1 245 405872753
2 47
1 144 574229391
2 180
1 52 933223793
2 105
1 263 234569527
2 18
2 10
2 22
1 186 298520436
2 41
2 212
2 74
1 50 246345024
2 9
1 208 234569527
1 76 856960762
1 297 405872753
2 151
1 96 296010479
1 149 1458624
1 269 298520436
1 17 629318818
1 223 1458624
2 214
1 146 856960762
2 227
1 229 246345024
2 165
1 231 679986156
2 157
1 292 172426594
1 124 405872753
1 91 121412483
2 7
1 272 629318818
2 293
1 140 800165334
1 283 296010479
1 268 933223793
2 157
1 180 800165334
2 50
1 21 46472898
2 110
1 239 298520436
1 113 296010479
1 266 1458624
2 136
1 276 234569527
2 254
2 119
2 188
1 183 1458624
2 105
1 267 856960762
2 275
1 203 202374341
2 119
1 24 296010479
2 263
1 13 246345024
2 181
1 239 856960762
2 75
1 84 933223793
2 252
1 51 933223793
2 289
1 259 1458624
2 214
1 24 800165334
1 41 457674832
1 111 1458624
2 108
2 80
2 168
1 173 296010479
2 10
1 26 933223793
2 202
1 149 172426594
2 119
1 17 92620085
2 136
1 210 298520436
2 206
1 226 800165334
2 275
1 165 46472898
2 260
1 21 92620085
2 244
1 8 296010479
2 88
1 263 800165334
1 45 92620085
1 56 933223793
2 180
1 291 574229391
2 37
1 209 246345024
2 295
1 142 679986156
2 196
1 22 202374341
2 292
1 271 457674832
2 70
1 132 629318818
2 293
1 131 121412483
2 255
1 293 92620085
2 54
1 252 46472898
2 146
1 148 202374341
2 130
1 190 1458624
2 268
1 90 933223793
2 274
2 43
2 222
1 221 246345024
2 76
1 143 296010479
2 275
1 11 457674832
1 57 52839209
1 94 405872753
2 26
1 151 234569527
2 4
1 190 457674832
2 14
2 41
2 7
1 139 574229391
2 180
2 211
2 215
1 148 202374341
1 41 92620085
1 287 52839209
1 176 174169584
1 298 121412483
2 89
1 272 679986156
2 290
1 14 856960762
2 111
1 189 574229391
2 238
1 108 234569527
2 224
1 205 92620085
1 83 121412483
2 146
1 201 202374341
1 35 457674832
2 47
1 74 405872753
1 131 234569527
2 141
1 117 246345024
1 61 52839209
2 173
1 253 172426594
1 37 174169584
1 36 52839209
2 100
1 190 629318818
2 169
1 228 574229391
2 63
1 82 121412483
1 75 629318818
1 172 92620085
2 174
1 240 202374341
2 297
1 131 52839209
2 294
1 125 172426594
2 195
1 203 202374341
2 166
1 126 296010479
2 223
1 43 800165334
2 161
1 103 298520436
2 139
1 191 856960762
1 67 202374341
1 153 457674832
2 97
1 158 574229391
2 223
1 123 1458624
2 156
1 159 800165334
1 44 933223793
1 269 121412483
2 99
1 88 92620085
2 204
1 28 1458624
2 229
2 99
2 146
1 61 246345024
2 160
1 174 121412483
2 97
1 42 1458624
1 152 121412483
1 108 457674832
2 10
1 68 679986156
2 139
1 276 121412483
2 187
1 61 574229391
2 6
1 227 46472898
2 30
1 37 246345024
1 139 405872753
1 241 405872753
1 230 629318818
1 54 246345024
2 260
1 188 46472898
2 157
1 78 629318818
2 68
1 239 457674832
2 50
1 102 174169584
2 175
1 40 629318818
2 35
1 266 296010479
2 264
1 213 121412483
2 165
1 112 92620085
1 153 679986156
1 132 172426594
2 53
1 15 121412483
2 174
1 14 933223793
2 72
1 105 298520436
2 279
1 92 457674832
2 268
2 122
2 80
Sample 3 Output
256
199
257
246
39
162
35
211
195
150
137
268
298
292
128
168
130
207
139
93
130
240
193
259
272
236
83
141
222
145
23
149
159
123
136
53
123
136
119
265
268
30
163
240
72
31
131
22
62
38
218
25
104
215
68
255
80
31
261
38
72
57
232
177
260
117
299
163
89
103
58
56
156
276
126
297
29
194
185
270
74
283
117
169
209
136
262
199
54
158
136
5
100
72
277
93
145
164
224
182
4
182
208
121
10
40
11
183
228
224
11
53
293
57
153
293
277
39
221
254
227
136
218
18
64
135
249
145
78
209
188
24
130
77
291
158
298
133
213
该测试点数据范围同测试点 $3 \sim 7$。