Kevin był uczestnikiem Codeforces. Niedawno zespół KDOI stworzył nowy system sędziowski online o nazwie Forcescode.

Kevin wziął udział w $n$ konkursach na Forcescode. W $i$-tym konkursie jego wynik (rating) wynosił $a_i$.

Teraz Kevin włamał się do backendu Forcescode i wybierze przedział $[l, r]$ ($1 \le l \le r \le n$), a następnie pominie wszystkie konkursy w tym przedziale. Po tym jego rating zostanie przeliczony w następujący sposób:

• Początkowo jego rating wynosi $x = 0$;
• Dla każdego $1 \le i \le n$, po $i$-tym konkursie:
  • Jeśli $l \le i \le r$, konkurs ten zostanie pominięty, a rating pozostanie bez zmian;
  • W przeciwnym razie jego rating zostanie zaktualizowany zgodnie z następującymi regułami:
    • Jeśli $a_i > x$, jego rating $x$ wzrośnie o 1;
    • Jeśli $a_i = x$, jego rating $x$ pozostanie bez zmian;
    • Jeśli $a_i < x$, jego rating $x$ zmaleje o 1.

Musisz pomóc Kevinowi znaleźć maksymalny możliwy rating po przeliczeniu, jeśli wybierze on przedział $[l, r]$ optymalnie. Zauważ, że Kevin musi pominąć co najmniej jeden konkurs.

Wejście

Każdy test zawiera wiele przypadków testowych. Pierwsza linia wejścia zawiera jedną liczbę całkowitą $t$ ($1 \le t \le 5 \cdot 10^4$) — liczbę przypadków testowych. Następnie podane są opisy przypadków testowych.

Pierwsza linia każdego przypadku testowego zawiera jedną liczbę całkowitą $n$ ($1 \le n \le 3 \cdot 10^5$) — liczbę konkursów.

Druga linia zawiera $n$ liczb całkowitych $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — wyniki w konkursach.

Gwarantuje się, że suma $n$ we wszystkich przypadkach testowych nie przekracza $3 \cdot 10^5$.

Wyjście

Dla każdego przypadku testowego wyprowadź jedną liczbę całkowitą — maksymalny możliwy rating po przeliczeniu, jeśli Kevin wybierze przedział optymalnie.

Przykład

Wejście 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

Wyjście 1

5
4
0
4
5

Uwagi

W pierwszym przypadku testowym Kevin musi pominąć co najmniej jeden konkurs. Jeśli wybierze dowolny przedział o długości 1, jego rating po przeliczeniu będzie równy 5.

W drugim przypadku testowym optymalnym wyborem Kevina jest przedział $[3, 5]$. Podczas przeliczania jego rating zmienia się następująco:

$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$

W trzecim przypadku testowym Kevin musi pominąć jedyny konkurs, więc jego rating pozostanie na wartości początkowej 0.

W czwartym przypadku testowym optymalnym wyborem Kevina jest przedział $[7, 9]$. Podczas przeliczania jego rating zmienia się następująco:

$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$

W piątym przypadku testowym optymalnym wyborem Kevina jest przedział $[5, 9]$. Podczas przeliczania jego rating zmienia się następująco:

$0 \xrightarrow{a_1=1} 1 \xrightarrow{a_2=2} 2 \xrightarrow{a_3=3} 3 \xrightarrow{a_4=4} 4 \xrightarrow{\text{skip}} 4 \xrightarrow{\text{skip}} 4 \xrightarrow{\text{skip}} 4 \xrightarrow{\text{skip}} 4 \xrightarrow{\text{skip}} 4 \xrightarrow{a_{10}=10} 5$