做完其他题后才能做的题

    钱陶陶家门前有一棵苹果树。 秋天来了，树上的n个苹果成熟了，淘淘会去采摘这些苹果。

    到园子里摘苹果时，淘淘将这些苹果从第一个苹果扫到最后一个。 如果当前的苹果是第一个苹果，或者它严格高于之前选择的苹果，那么淘淘将采摘这个苹果; 否则，他不会选择。

    题目来了：已知这些苹果的高度为h₁，h₂，⋯，h_n，您需要回答一些独立的查询。 每个查询是两个整数p，q，表示如果第p个苹果的高度修改为q，询问当前淘淘将摘到的苹果的数量。 你能解决这个问题吗？

输入的第一行是整数T，代表测试数据的组数

每组测试数据第一行包含两个整数n，m（1<=n，m<=10⁵，表示苹果的数量和查询的数量。

接着是一行n个整数h₁，h₂，……，h_n（1<=h_i<=10⁹），表示苹果的高度。

再接下来m行给出查询。

每行包含两个整数p（1<=p<＝n）和q（1<=q <＝10⁹）.

对于每组数据输出一行代表查询的结果

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

1
5
3

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

1
2
2
2

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

1
5
3
2
2
2
1

 Note

对于第二个样例
四次查询的对象分别是
1 1 1 1
1 2 1 1
1 1 3 1
1 1 1 4
所以答案也很明显的是
1
2
2
2