#P18019. Maximum Difference
Maximum Difference
Maximum Difference
对一个数组 ,定义 如下。
开始时令 。每次操作选择当前数组中一个非空子序列 ,然后:
- 令 。
- 将选中的元素按非递减顺序排序,再按原来选中位置的先后顺序,写回这些位置。
可以进行任意次操作。能够使整个数组变成非递减数组的操作序列中,最终 的最小值就是 。如果数组初始已经非递减,则分数为 。
给定长度为 的数组 ,以及 次修改。每次修改给出 ,令 。修改会保留并影响后续修改。
在每次修改之后输出当前数组的 。这里只是在计算该分数,定义中的排序操作不会实际改变后续修改使用的数组。
输入格式
第一行一个整数 。每组数据的格式如下:
- 第一行两个整数 。
- 第二行 个整数 。
- 接下来 行,每行两个整数 ,描述一次修改。
输出格式
每次修改后输出一行一个整数,表示当前数组的分数。
数据范围
,,,。
所有测试用例的 之和不超过 , 之和也不超过 。
样例 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