CF2057D.Gifts Order

“T-Generation” 队计划采购一些毛衣以满足多种需求，他们拥有 $n$ 件毛衣编号从 $1$ 至 $n$。第 $i$ 件毛衣的尺寸为 $a_i$。现在，他们需要选出某段连续的毛衣送去参加奥林匹克竞赛。这些毛衣必须尽可能适合更多的人，同时又不能选择得太多。

他们需要选择两个下标 $l$ 和 $r$（$1 \le l \le r \le n$），使便利性最大化。便利性定义为 $\operatorname{max}(a_l, a_{l + 1}, \ldots, a_r) - \operatorname{min}(a_l, a_{l + 1}, \ldots, a_r) - (r - l)$，也就是尺寸的范围减去所选毛衣数量。

考虑到毛衣的尺寸可能会发生变化，总共有 $q$ 次这样的变动。每次变化中，第 $p$ 件毛衣的尺寸变为 $x$。

请帮助 “T-Generation” 团队计算出在所有可能的 $(l, r)$ 对中，初次和每次尺寸调整后的最大便利性。

输入包含多个测试用例。第一行是一个整数 $t$（$1 \le t \le 10^4$）表示测试用例的数量。随后是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 2 \cdot 10^5$），分别表示毛衣总数和尺寸变化的次数。

接下来的第二行包括 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示每件毛衣的尺寸。

此后 $q$ 行，每行包含两个整数 $p$ 和 $x$（$1 \le p \le n$, $1 \le x \le 10^9$），表示一次尺寸变化，第 $p$ 件毛衣的尺寸变为 $x$。

保证所有测试用例中所有 $n$ 的总和以及所有 $q$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出在操作前以及每次尺寸变化后，所有可能的 $(l, r)$ 对中最大便利性。

来看第一个测试用例的情况：

• 在没有变化之前，可以选取所有毛衣，此时便利性等于 $\operatorname{max}(a_1, a_2) - \operatorname{min}(a_1, a_2) - (2 - 1) = 10 - 1 - 1 = 8$。
• 第一次查询后，两件毛衣的尺寸都变为 $10$，只能选取第一件毛衣，此时便利性等于 $10 - 10 - 0 = 0$。
• 第二次查询后，第一件毛衣的尺寸为 $10$，第二件为 $2$，可以选取所有毛衣，便利性为 $\operatorname{max}(a_1, a_2) - \operatorname{min}(a_1, a_2) - (2 - 1) = 10 - 2 - 1 = 7$。

本翻译由 AI 自动生成