“T一代”决定购买礼物以满足各种需求;因此,他们有 $$$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 一代”团队并确定所有可能的对 $$$(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$$$) - 下一个大小更改。
保证所有测试用例中 $$$n$$$ 的值之和以及 $$$q$$$ 的值之和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,在任何操作之前以及每次大小更改之后输出所有可能对 $$$(l, r)$$$ 中便利性的最大值。
示例
输入 #1
3 2 2 1 10 1 10 2 2 5 3 1 2 3 4 5 3 7 1 4 5 2 8 5 7 4 2 4 8 2 1 4 5 4 1 10 3 2 8 11 7 7
输出 #1
8 0 7 0 4 4 4 5 3 6 6 9 7
注意
考虑第一个测试用例。
- 在进行任何更改之前,您可以拿走所有毛衣;那么方便性就等于 $$$\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$$$。