题不算难，但是思想非常值得借鉴。

题意是给出序列 ，若干次单点修改。修改后求出如果对序列 进行冒泡排序，外层循环至少需要执行几次才能使得 不降。

首先有广为人知的结论：答案等于 ，证明大概是每进行一趟冒泡，每个数前面比它大的数的个数就会减少 。

接下来考虑怎么统计这个东西。

容易发现如果一个点 存在 且 ，那么 对那个 是完全没有贡献的。

否则， 后面没有比 小的数，那么 前面比 大的数的个数就是 。（这里的二元组比较是先比第一维，再比第二维）

因为总共只有 个不同的 ，询问还可以离线，我们把所有可能的 进行离散化，然后开一个值域线段树维护上面那个式子的最大值即可。

时间复杂度