【题目描述】

插入排序是一种非常常见且简单的排序算法。

小 Z 是一名大一的新生，今天 H 老 师刚刚在上课的时候讲了插入排序算法。 假设比较两个元素的时间为 O(1)，则插入排序可以以 O(n 2 ) 的时间复杂度完成长 度为 n 的数组的排序。不妨假设这 n 个数字分别存储在 a1, a2, · · · , an 之中，则如下伪 代码给出了插入排序算法的一种最简单的实现方式： 

这下面是 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 个元素，也就是 ax 的值，修改为 v。保证 1 ≤ x ≤ n, 1 ≤ v ≤ 109。注意这种操作会改变数组的元素， 修改得到的数组会被保留，也会影 响后续的操作。.

 2 x : 这是第二种操作，假设 H 老师按照上. 面. 的. 伪. 代. 码. 对 a 数组进行排序，你需要 告诉 H 老师原来 a 的第 x 个元素，也就是 ax，在排序后的新数组所处的位置。保证 1 ≤ x ≤ n。注意这种操作不会改变数组的元素，排序后的数组不会被保留，也不会影响后续的操作。

H 老师不喜欢过多的修改，所以他保证类型 1 的操作次数不超过 5000。 

小 Z 没有学过计算机竞赛，因此小 Z 并不会做这道题。他找到了你来帮助他解决 这个问题。

【输入格式】

从文件 sort.in 中读入数据。 

输入的第一行包含两个正整数 n, Q，表示数组长度和操作次数。保证 1 ≤ n ≤ 8, 000, 1 ≤ Q ≤ 2 × 105。 输入的第二行包含 n 个空格分隔的非负整数，其中第 i 个非负整数表示 ai。保证 1 ≤ ai ≤ 109。 接下来 Q 行，每行 2 ∼ 3 个正整数，表示一次操作，操作格式见题目描述。

【输出格式】

输出到文件 sort.out 中。 对于每一次类型为 2 的询问，输出一行一个正整数表示答案。

【样例1输入】

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

【样例1输出】

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 次操作属于类型一。 各测试点的附加限制及分值如下表所示。

【题目背景】

红太阳幼儿园的小朋友们开始分糖果啦！

【题目描述】

红太阳幼儿园有 n 个小朋友，你是其中之一。保证 n ≥ 2。 

有一天你在幼儿园的后花园里发现无穷多颗糖果，你打算拿一些糖果回去分给幼儿 园的小朋友们。 

由于你只是个平平无奇的幼儿园小朋友，所以你的体力有限，至多只能拿 R 块糖 回去。 

但是拿的太少不够分的，所以你至少要拿 L 块糖回去。保证 n ≤ L ≤ R。 

也就是说，如果你拿了 k 块糖，那么你需要保证 L ≤ k ≤ R。 

如果你拿了 k 块糖，你将把这 k 块糖放到篮子里，并要求大家按照如下方案分糖 果：只要篮子里有不. 少. 于. n 块糖果，幼儿园的所有 n 个小朋友（包括你自己）都从篮子 中拿走恰. 好. 一块糖，直到篮子里的糖数量少. 于. n 块。此时篮子里剩余的糖果均归你所有 ——这些糖果是作. 为. 你. 搬. 糖. 果. 的. 奖. 励. 。 

作为幼儿园高质量小朋友，你希望让作. 为. 你. 搬. 糖. 果. 的. 奖. 励. 的糖果数量（而. 不. 是. 你. 最. 后. 获. 得. 的. 总. 糖. 果. 数. 量！. ）尽可能多；因此你需要写一个程序，依次输入 n, L, R，并输出 出你最多能获得多少作. 为. 你. 搬. 糖. 果. 的. 奖. 励. 的糖果数量。

【输入格式】

从文件 candy.in 中读入数据。 

输入一行，包含三个正整数 n, L, R，分别表示小朋友的个数、糖果数量的下界和上 界。

【输出格式】

输出到文件 candy.out 中。 

输出一行一个整数，表示你最多能获得的作. 为. 你. 搬. 糖. 果. 的. 奖. 励. 的糖果数量。

【样例1输入】

7 16 23

【样例1输出】

6

【样例1解释】

拿 k = 20 块糖放入篮子里。 

篮子里现在糖果数 20 ≥ n = 7，因此所有小朋友获得一块糖；

篮子里现在糖果数变成 13 ≥ n = 7，因此所有小朋友获得一块糖； 

篮子里现在糖果数变成 6 < n = 7，因此这 6 块糖是作. 为. 你. 搬. 糖. 果. 的. 奖. 励. 。 

容易发现，你获得的作. 为. 你. 搬. 糖. 果. 的. 奖. 励. 的糖果数量不可能超过 6 块（不然，篮子 里的糖果数量最后仍然不少于 n，需要继续每个小朋友拿一块），因此答案是 6。

【样例2输入】

10 14 18

【样例2输出】

8

【样例2解释】

容易发现，当你拿的糖数量 k 满足 14 = L ≤ k ≤ R = 18 时，所有小朋友获得一块 糖后，剩下的 k − 10 块糖总是作. 为. 你. 搬. 糖. 果. 的. 奖. 励. 的糖果数量，因此拿 k = 18 块是最 优解，答案是 8。

【数据范围】

对于所有数据，保证 2 ≤ n ≤ L ≤ R ≤ 109。