Кевин раньше участвовал в соревнованиях на 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, \dots, a_n$ ($1 \le a_i \le n$) — рейтинги результативности в соревнованиях.

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

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

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

Примеры

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

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

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

5
4
0
4
5

Примечание

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

Во втором наборе входных данных оптимальный выбор Кевина — интервал $[3, 5]$. Во время пересчета его рейтинг меняется следующим образом: $$0 \xrightarrow{a_1=1} 1 \xrightarrow{a_2=2} 2 \xrightarrow{\text{skip}} 2 \xrightarrow{\text{skip}} 2 \xrightarrow{\text{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{\text{skip}} 4 \xrightarrow{\text{skip}} 4 \xrightarrow{\text{skip}} 4$$

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