Kevin solía participar en Codeforces. Recientemente, el equipo KDOI ha desarrollado un nuevo juez en línea llamado Forcescode.

Kevin ha participado en $n$ concursos en Forcescode. En el $i$-ésimo concurso, su calificación de desempeño es $a_i$.

Ahora, él ha hackeado el backend de Forcescode y seleccionará un intervalo $[l, r]$ ($1 \le l \le r \le n$), para luego omitir todos los concursos en este intervalo. Después de eso, su calificación será recalculada de la siguiente manera:

• Inicialmente, su calificación es $x = 0$;
• Para cada $1 \le i \le n$, después del $i$-ésimo concurso:
  • Si $l \le i \le r$, este concurso será omitido y la calificación permanecerá sin cambios;
  • De lo contrario, su calificación será actualizada de acuerdo con las siguientes reglas:
    • Si $a_i > x$, su calificación $x$ aumentará en 1;
    • Si $a_i = x$, su calificación $x$ permanecerá sin cambios;
    • Si $a_i < x$, su calificación $x$ disminuirá en 1.

Debes ayudar a Kevin a encontrar su máxima calificación posible después del recálculo si elige el intervalo $[l, r]$ de manera óptima. Ten en cuenta que Kevin debe omitir al menos un concurso.

Entrada

Cada prueba contiene múltiples casos de prueba. La primera línea de la entrada contiene un único entero $t$ ($1 \le t \le 5 \cdot 10^4$) — el número de casos de prueba. A continuación se presenta la descripción de los casos de prueba.

La primera línea de cada caso de prueba contiene un único entero $n$ ($1 \le n \le 3 \cdot 10^5$) — el número de concursos.

La segunda línea contiene $n$ enteros $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — las calificaciones de desempeño en los concursos.

Se garantiza que la suma de $n$ sobre todos los casos de prueba no excede $3 \cdot 10^5$.

Salida

Para cada caso de prueba, imprime un único entero — la máxima calificación posible después del recálculo si Kevin elige el intervalo de manera óptima.

Ejemplos

Entrada 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

Salida 1

5
4
0
4
5

Nota

En el primer caso de prueba, Kevin debe omitir al menos un concurso. Si elige cualquier intervalo de longitud 1, su calificación después del recálculo será igual a 5.

En el segundo caso de prueba, la elección óptima de Kevin es seleccionar el intervalo $[3, 5]$. Durante el recálculo, su calificación cambia de la siguiente manera:

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

En el tercer caso de prueba, Kevin debe omitir el único concurso, por lo que su calificación permanecerá en el valor inicial de 0.

En el cuarto caso de prueba, la elección óptima de Kevin es seleccionar el intervalo $[7, 9]$. Durante el recálculo, su calificación cambia de la siguiente manera:

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

En el quinto caso de prueba, la elección óptima de Kevin es seleccionar el intervalo $[5, 9]$. Durante el recálculo, su calificación cambia de la siguiente manera:

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