Kevin은 과거 Codeforces의 참가자였습니다. 최근 KDOI 팀은 Forcescode라는 새로운 온라인 저지를 개발했습니다.

Kevin은 Forcescode에서 $n$번의 콘테스트에 참가했습니다. $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 감소합니다.

Kevin이 구간 $[l, r]$을 최적으로 선택했을 때, 재계산 후 얻을 수 있는 최대 등급을 구하도록 도와주세요. Kevin은 반드시 최소 하나의 콘테스트를 건너뛰어야 합니다.

입력

각 테스트 케이스는 여러 개의 테스트 케이스를 포함합니다. 입력의 첫 번째 줄에는 테스트 케이스의 수 $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$을 넘지 않음이 보장됩니다.

출력

각 테스트 케이스마다 Kevin이 구간을 최적으로 선택했을 때 재계산 후 얻을 수 있는 최대 등급을 정수로 출력합니다.

예제

입력 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

참고

첫 번째 테스트 케이스에서 Kevin은 최소 하나의 콘테스트를 건너뛰어야 합니다. 길이가 1인 임의의 구간을 선택하면, 재계산 후 그의 등급은 5가 됩니다.

두 번째 테스트 케이스에서 Kevin의 최적 선택은 구간 $[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$$

세 번째 테스트 케이스에서 Kevin은 유일한 콘테스트를 건너뛰어야 하므로, 그의 등급은 초기값인 0으로 유지됩니다.

네 번째 테스트 케이스에서 Kevin의 최적 선택은 구간 $[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$$

다섯 번째 테스트 케이스에서 Kevin의 최적 선택은 구간 $[5, 9]$를 선택하는 것입니다. 재계산 과정에서 그의 등급은 다음과 같이 변합니다.

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