Kevin était autrefois un participant sur Codeforces. Récemment, l'équipe KDOI a développé un nouveau juge en ligne appelé Forcescode.

Kevin a participé à $n$ concours sur Forcescode. Lors du $i$-ème concours, sa performance est notée $a_i$.

Maintenant, il a piraté le backend de Forcescode et va choisir un intervalle $[l, r]$ ($1 \le l \le r \le n$), puis ignorer tous les concours dans cet intervalle. Après cela, sa note sera recalculée de la manière suivante :

• Initialement, sa note est $x = 0$ ;
• Pour chaque $1 \le i \le n$, après le $i$-ème concours :
  • Si $l \le i \le r$, ce concours est ignoré et la note reste inchangée ;
  • Sinon, sa note est mise à jour selon les règles suivantes :
    • Si $a_i > x$, sa note $x$ augmente de 1 ;
    • Si $a_i = x$, sa note $x$ reste inchangée ;
    • Si $a_i < x$, sa note $x$ diminue de 1.

Vous devez aider Kevin à trouver la note maximale possible après le recalcul s'il choisit l'intervalle $[l, r]$ de manière optimale. Notez que Kevin doit ignorer au moins un concours.

Entrée

Chaque test contient plusieurs cas de test. La première ligne de l'entrée contient un entier unique $t$ ($1 \le t \le 5 \cdot 10^4$) — le nombre de cas de test. La description des cas de test suit.

La première ligne de chaque cas de test contient un entier unique $n$ ($1 \le n \le 3 \cdot 10^5$) — le nombre de concours.

La deuxième ligne contient $n$ entiers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — les notes de performance dans les concours.

Il est garanti que la somme de $n$ sur tous les cas de test ne dépasse pas $3 \cdot 10^5$.

Sortie

Pour chaque cas de test, affichez un entier unique — la note maximale possible après le recalcul si Kevin choisit l'intervalle de manière optimale.

Exemples

Entrée 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

Sortie 1

5
4
0
4
5

Remarque

Dans le premier cas de test, Kevin doit ignorer au moins un concours. S'il choisit n'importe quel intervalle de longueur 1, sa note après le recalcul sera égale à 5.

Dans le deuxième cas de test, le choix optimal de Kevin est de sélectionner l'intervalle $[3, 5]$. Lors du recalcul, sa note change comme suit :

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

Dans le troisième cas de test, Kevin doit ignorer le seul concours, donc sa note restera à la valeur initiale de 0.

Dans le quatrième cas de test, le choix optimal de Kevin est de sélectionner l'intervalle $[7, 9]$. Lors du recalcul, sa note change comme suit :

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

Dans le cinquième cas de test, le choix optimal de Kevin est de sélectionner l'intervalle $[5, 9]$. Lors du recalcul, sa note change comme suit :

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