陈远龙精品编程（信奥赛） 助力信奥赛学子取得优秀的成绩

题目描述

老师给了一个长度为 $n$ 的数组 $a$，数组下标从 $1$ 开始，这个数组一开始已经从小到大排好序了，数组下标从1开始，现在修改其中一个位置上的值，然后需要对这组数重新排序，问你排序后这组数中第x位的数是多少？

输入格式

第1行，一个正整数n和一个正整数Q，分别代码这组数的个数和询问次数

第2行，有n个整数，每个整数使用空格分隔，代表这n个数

接下来有Q行，每行一个2 - 3个正整数，格式如下：

1 x v，1代表修改操作，将数组的x位置修改为v

2 x，2代表查询操作，查询数组排序后的x位置的值

注意每次操作（包括1、2）都是在原数组中进行的，也就是前一次修改或查询对后续的操作是有影响的

同时1操作和2操作是交替出现的，也就是出现1次操作1，后续就会有1次操作2，类似于

1 2 3
2 3
1 3 4
2 5

这种格式，保证第1次是操作1

输出格式

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

输入输出样例 #1

输入 #1

5 4
1 3 5 7 9
1 2 6
2 3
1 4 -1
2 3

输出 #1

6
5

说明/提示

对于 $50%$ 的数据，$1 \le n \le 8000,1 \le Q \le 2 \times 10^3$，$1 \le x \le n$，$-10^9 \le v,a_i \le 10^9$，$Q$为偶数

对于 $100%$ 的数据，$1 \le n \le 8000,1 \le Q \le 2 \times 10^5$，$1 \le x \le n$，$-10^9 \le v,a_i \le 10^9$，$Q$为偶数

此题为 P1200-插入排序【CSP-J 2021 入门级 T2】 的简化版

测试点数目

共10个测试点，每个测试点10分

时间与内存限制

每个测试点时间：1000ms（1.0s），内存：512MiB

输入输出模式

本OJ支持两种输入输出模式