C. Новый рейтинг
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Привет, Codeforces Forcescode!
 

Кевин раньше был участником Codeforces. Недавно команда KDOI разработала новый сайт под названием Forcescode.

Кевин принял участие в $$$n$$$ соревнованиях на Forcescode. В $$$i$$$-м соревновании его рейтинг выступления равен $$$a_i$$$.

Теперь он взломал бэкенд Forcescode и выберет отрезок $$$[l,r]$$$ ($$$1\le l\le r\le n$$$), после чего он пропустит все соревнования в этом отрезке. После этого его рейтинг будет пересчитан следующим образом:

  • Изначально его рейтинг равен $$$x=0$$$;
  • Для каждого $$$1\le i\le n$$$, после $$$i$$$-го соревнования,
    • Если $$$l\le i\le r$$$, это соревнование будет пропущено, и рейтинг не изменится;
    • В противном случае его рейтинг будет обновлен в соответствии со следующими правилами:
      • Если $$$a_i>x$$$, его рейтинг $$$x$$$ увеличится на $$$1$$$;
      • Если $$$a_i=x$$$, его рейтинг $$$x$$$ останется без изменений;
      • Если $$$a_i<x$$$, его рейтинг $$$x$$$ уменьшится на $$$1$$$.

Вам нужно помочь Кевину найти его максимальный возможный рейтинг после пересчета, если он оптимально выберет отрезок $$$[l,r]$$$. Обратите внимание, что Кевин должен пропустить как минимум одно соревнование.

Входные данные

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

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

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

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

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимальный возможный рейтинг после пересчета, если Кевин выберет интервал оптимально.

Пример
Входные данные
5
6
1 2 3 4 5 6
7
1 2 1 1 1 3 4
1
1
9
9 9 8 2 4 4 3 5 3
10
1 2 3 4 1 3 2 1 1 10
Выходные данные
5
4
0
4
5
Примечание

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

Во втором наборе входных данных оптимальный выбор Кевина — отрезок $$$[3,5]$$$. Во время пересчета его рейтинг изменяется следующим образом:

$$$$$$ 0 \xrightarrow{a_1=1} 1 \xrightarrow{a_2=2} 2 \xrightarrow{\mathtt{skip}} 2 \xrightarrow{\mathtt{skip}} 2 \xrightarrow{\mathtt{skip}} 2 \xrightarrow{a_6=3} 3 \xrightarrow{a_7=4} 4 $$$$$$

В третьем наборе входных данных Кевин должен пропустить единственное соревнование, поэтому его рейтинг останется равным $$$0$$$.

В четвертом наборе входных данных оптимальный выбор Кевина — отрезок $$$[7,9]$$$. Во время пересчета его рейтинг изменяется следующим образом:

$$$$$$ 0 \xrightarrow{a_1=9} 1 \xrightarrow{a_2=9} 2 \xrightarrow{a_3=8} 3 \xrightarrow{a_4=2} 2 \xrightarrow{a_5=4} 3 \xrightarrow{a_6=4} 4 \xrightarrow{\mathtt{skip}} 4 \xrightarrow{\mathtt{skip}} 4 \xrightarrow{\mathtt{skip}} 4 $$$$$$

В пятом наборе входных данных оптимальный выбор Кевина — отрезок $$$[5,9]$$$.