Подкрутка II
Contest: VK Cup 2022 - Квалификация (Engine)
Difficulty rating: 1300
Tags: *special, dp

В этой версии задачи $$$n \le 2 \cdot 10^5$$$ и $$$a_i \le 10^6$$$ (а также есть ограничение на сумму $$$n$$$ по наборам входных данных внутри одного теста).

Вика за время работы в компании VK уже сделала $$$n$$$ коммитов в системе контроля версий. $$$i$$$-й коммит был сделан в $$$a_i$$$-й день работы Вики в компании. В некоторые дни Вика могла сделать несколько коммитов, а в другие — не сделать ни одного.

Вику интересуют такие отрезки подряд идущих дней, что в каждый из этих дней у неё есть хотя бы один коммит. Чем длиннее будет самый длинный такой отрезок, тем более продуктивным сотрудником она будет себя ощущать.

Недавно Вика нашла способ подкрутить время любого коммита вперёд, но не более чем на сутки. Таким образом, $$$i$$$-й коммит теперь может быть «сделан» либо в $$$a_i$$$-й, либо в $$$(a_i + 1)$$$-й день. Время каждого коммита можно подкрутить независимо от других — в частности, можно как оставить всем коммитам исходное время, так и перенести все коммиты ровно на день вперёд.

Найдите длину самого длинного возможного отрезка подряд идущих дней, в каждый из которых у Вики в профиле будет отображаться хотя бы один коммит, после возможной подкрутки времени некоторых коммитов.

Input format:
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — число коммитов.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ в неубывающем порядке ($$$1 \le a_1 \le a_2 \le \ldots \le a_n \le 10^6$$$) — номера дней, в которые были сделаны коммиты.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Output format:
Для каждого набора входных данных выведите одно целое число — максимальную возможную длину отрезка дней, в каждый из которых у Вики в профиле будет отображаться хотя бы один коммит, после возможной подкрутки времени некоторых коммитов вперёд не более чем на сутки.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
В первом наборе входных данных можно поменять дату коммита в день $$$3$$$ на день $$$4$$$, дату коммита в день $$$4$$$ — на день $$$5$$$, а дату любого из коммитов в день $$$6$$$ — на день $$$7$$$. Тогда в каждый из дней $$$4$$$, $$$5$$$, $$$6$$$, $$$7$$$ и $$$8$$$ в профиле Вики будет отображаться хотя бы один коммит, и наибольший отрезок из подряд идущих дней с коммитами — $$$[4; 8]$$$ — будет иметь длину $$$5$$$.

Во втором наборе входных данных можно либо оставить все коммиты как есть, либо перенести каждый коммит на день вперёд. В любом случае длина отрезка дней составит $$$6$$$.

В третьем наборе входных данных Вика сделала много коммитов, но все в один и тот же день с номером $$$10$$$. В лучшем случае отрезок дней достигнет длины $$$2$$$ — если какие-то коммиты оставить на день $$$10$$$, а другие перенести на день $$$11$$$.

Example input:
3
9
1 1 3 4 6 6 6 8 10
6
1 2 3 4 5 6
5
10 10 10 10 10

Example output:
5
6
2

Editorial:
Первую версию задачи можно решать следующим образом. Переберём день, с которого может начаться искомый наибольший отрезок. Пойдём по коммитам в хронологическом порядке и попробуем продлить отрезок дней каждым из них, если это возможно. Таким образом для каждого начального дня отрезка мы получим как можно более поздний конечный день, а ответ на задачу будет равен длине наибольшего из всех найденных отрезков.
Сложность решения составит $$$O((a_n - a_1) \cdot n)$$$.
Пример решения первой версии на Python:
Есть несколько вариантов решения второй версии задачи. Представим решение при помощи динамического программирования. Пусть $$$f(i, j)$$$ равно длине максимального отрезка дней, заканчивающегося коммитом номер $$$i$$$, если сам этот коммит был сдвинут на $$$j$$$ дней вперёд ($$$1 \le i \le n$$$; $$$0 \le j \le 1$$$). Чтобы вычислить $$$f(i, j)$$$, переберём сдвиг предыдущего коммита $$$k$$$ ($$$0 \le k \le 1$$$) и вычислим разность между новыми днями коммитов: $$$d = (a_i + j) - (a_{i - 1} + k)$$$. Если значение разности $$$d$$$ лежит в диапазоне от $$$0$$$ до $$$1$$$, значит, отрезок, заканчивавшийся коммитом номер $$$i - 1$$$, сдвинутым на $$$k$$$ дней вперёд, может продолжиться при данных условиях, и новая длина отрезка составит $$$f(i - 1, k) + d$$$ дней.
Ответом на задачу будет являться максимум по всем найденным значениям $$$f(i, j)$$$.
Сложность решения составит $$$O(n)$$$.
Пример решения второй версии на Python: