D. Заказ мерча
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

«Т-поколение» решило закупить мерч на различные нужды, таким образом, у них есть $$$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$$$.

Помогите кружку и определите максимальное значение удобства среди всех возможных пар $$$(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)$$$ до всех действий, а также после изменения размеров.

Пример
Входные данные
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
Выходные данные
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$$$.