Description

勇者闯得知了这个世界上还有一种神秘之力，勇者闯可以通过它提升战斗力。通过一阵打听，得知了这个神秘之力在土匪欢的手中。于是勇者闯找到了土匪欢，想要得到神秘之力。经过勇者闯一阵苦口婆心的劝说，土匪欢终于承受不住了。土匪欢说：“懂了懂了，你不就是想要这个神秘之力吗，我给你还不行吗？不过你要回答我的问题才行”

土匪欢将满足以下性质的数称之为力量数字：对于属于给定区间 [l,r] 中的第 i (i ∈[l，r]) 个正整数ai，若在给定的区间[l，r]中满足i = l或者在区间[l，i - 1]内的所有数都小于ai，那么土匪欢将这个数字ai称之为力量数字。

如：1，2，8，5，4这五个数中的1，2，8。

现在，土匪欢会给你n个正整数，并会将这n个正整数编号为1到n。现在土匪欢将会进行两种操作：

1.将编号为x的数字替换为y；

2.询问区间[l，r]内有多少个力量数字。

若想成功提升战斗力，勇者闯需要正确回答土匪欢的每次询问，勇者闯有点力不从心，你能帮帮他吗？

Input Format

第一行输入一个整数T表示测试样例数(1 ≤ T ≤ 10)

对于每组测试样例：

共会输入m + 2行。

第一行会输入两个正整数n和m(1≤n，m≤10^5)。

第二行会输入n个正整数ai(1≤ ai≤ 10^9)，表示土匪欢给出的那n个正整数。

接下来m行，每行会输入三个正整数op(1≤op≤2)，x，y。

当op等于1的时候，表示的是土匪欢的第一种操作，此时x(1≤ x≤ n)表示要修改的那个数的编号，y(1≤ y≤ 9)表示土匪欢要将这个数修改成哪个数。

当op等于2的时候，表示的是土匪欢的第二种操作，此时的x，y(1≤ x≤ y≤ n)表示的是土匪欢询问的那个区间的左端点和右端点的编号。

Output Format

对于土匪欢的每次询问，输出一行，该行包含一个正整数，表示此次询问的正确答案。

1
5 6
1 2 3 4 5
2 1 5
2 2 4
1 3 10
2 1 5
2 2 3
2 4 5

5
3
3
2
2

Hint

样例说明：

第一次询问：

此次询问的区间是[1，5]，很明显，这个区间内的5个数都是力量数字，所以我们输出5。

第二次询问：

此次询问的区间是[2，4]，很明显，这个区间内的3个数都是力量数字，所以我们输出3。

第一次修改：

此次修改将编号为3的数字的值修改为了10，修改后这n个数字依次是：1，2，10，4，5。

第三次询问：

此次询问的区间是[1，5]，我们可以知道，这个区间里的力量数字有三个，分别是：1，2，10。所以我们输出3。

第四次询问：

此次询问的区间是[2，3]，很明显，这个区间内的2个数都是力量数字，所以我们输出2。

第五次询问：

此次询问的区间是[4，5]，很明显，这个区间内的2个数都是力量数字，所以我们输出2。

Source

1816 Online Judge 10.100.0.232