#P18019. Maximum Difference

Maximum Difference

Maximum Difference

对一个数组 BB,定义 score⁡(B)\operatorname{score}(B) 如下。

开始时令 X=0X=0。每次操作选择当前数组中一个非空子序列 SS,然后:

  1. 令 X←max⁡(X,max⁡(S)−min⁡(S))X\leftarrow\max\bigl(X,\max(S)-\min(S)\bigr)。
  2. 将选中的元素按非递减顺序排序,再按原来选中位置的先后顺序,写回这些位置。

可以进行任意次操作。能够使整个数组变成非递减数组的操作序列中,最终 XX 的最小值就是 score⁡(B)\operatorname{score}(B)。如果数组初始已经非递减,则分数为 00。

给定长度为 NN 的数组 AA,以及 MM 次修改。每次修改给出 P,YP,Y,令 AP=YA_P=Y。修改会保留并影响后续修改。

在每次修改之后输出当前数组的 score⁡(A)\operatorname{score}(A)。这里只是在计算该分数,定义中的排序操作不会实际改变后续修改使用的数组。

输入格式

第一行一个整数 TT。每组数据的格式如下:

  • 第一行两个整数 N,MN,M。
  • 第二行 NN 个整数 A1,…,ANA_1,\ldots,A_N。
  • 接下来 MM 行,每行两个整数 P,YP,Y,描述一次修改。

输出格式

每次修改后输出一行一个整数,表示当前数组的分数。

数据范围

1≤T≤1041\le T\le10^4,1≤N,M≤5×1051\le N,M\le5\times10^5,1≤Ai,Y≤N1\le A_i,Y\le N,1≤P≤N1\le P\le N。

所有测试用例的 NN 之和不超过 5×1055\times10^5,MM 之和也不超过 5×1055\times10^5。

样例 1

输入

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

输出

3
0
2
1
1