时间限制：1秒　　内存限制：256M

---

【题目描述】

　　小H最近迷上了排序算法的学习，他掌握了选择排序、插入排序、冒泡排序、归并排序、快速排序、桶排序等。但作为初学者，目前为止他最喜欢的算法是“冒泡排序”。
　　冒泡排序可以以 O(N2) 的时间复杂度完成长度为 N 的数组的排序。不妨假设这 N 个数字分别存储在数组 A[0],A[1],…,A[N-1] 之中，则如下伪代码给出了冒泡排序算法的一种最简单的实现方式：

　　显然，伪代码码中指令cnt ← cnt+1的作用是记录进行了多少轮冒泡，用于研究该算法针对不同数据的执行效率。
现在输入数组A[0],A[1],…,A[N-1]，请预测小H的代码执行完后cnt的值。

　　为避免你在考场过于无聊，小H还要求你继续完成去年复赛的第二题《插入排序》的任务：请你完成Q次操作，操作分两种，格式如下：
　　1 x v: 这是第一种操作，会将数组 A 的第 x 个元素，也就是 A[x] 的值，修改为 v。保证 0≤x<N，1≤v≤109。注意这种操作会改变数组的元素，修改得到的数组会被保留，也会影响后续的操作。
　　2 x: 这是第二种操作，假设小H按照上面的伪代码对A[0],A[1],…,A[N-1]进行排序，你需要告诉小H 原来 A 的第x个元素，也就是A[x]，在排序后的新数组所处的位置。保证0≤x<N。注意这种操作不会改变数组的元素，排序后的数组不会被保留，也不会影响后续的操作。

【输入格式】

　　输入的第一行包含N 和 Q。
　　第二行描述了A[0],A[1],…,A[N-1]，每个数都是一个范围为0..109的整数。输入数据不保证各不相同。
　　接下来Q行，每行2∼3个正整数，表示一次操作，操作格式见题目描述。

【输出格式】

　　第一行输出一个整数，表示cnt的值。
　　接下来的若干行，对于每一次类型为2的询问，输出一行一个正整数表示答案。

【输入输出样例】

　Input

5 4
1 5 3 8 2 
2 4
1 4 3
2 4
2 2

　Output

4
1
2
1

【数据限制】

【来源】

　　Mr.he