크기가 $n$인 순열은 $1$부터 $n$까지의 모든 값이 정확히 한 번씩 나타나는 $n$개의 정수로 이루어진 수열 $a_1,a_2,\ldots,a_n$이다.

수열 $b_1,b_2,\ldots,b_l$이 수열 $a_1,a_2,\ldots,a_n$의 부분 수열이라는 것은 $a$에서 일부 원소를 삭제하여 $b$를 얻을 수 있다는 뜻이다. 즉, $l\le n$이고 $a_{i_t}=b_t$를 만족하는 $i_1<i_2<\cdots<i_l$이 존재한다.

• 수열의 원소 $a_i$가 앞에 있는 모든 원소보다 엄격히 크면 최고 기록이라고 한다. 즉, 모든 $1\le j<i$에 대해 $a_j<a_i$이다.
• 수열의 원소 $a_i$가 앞에 있는 모든 원소보다 엄격히 작으면 최저 기록이라고 한다. 즉, 모든 $1\le j<i$에 대해 $a_j>a_i$이다.

크기가 $n$인 순열 $p_1,p_2,\ldots,p_n$이 주어진다. 이를 비어 있지 않은 두 부분 수열 $q$와 $r$로 나누어야 한다. 다시 말해, $p$의 각 원소는 정확히 하나의 부분 수열에 포함되어야 한다. 이때 $q$의 최고 기록 개수와 $r$의 최저 기록 개수의 합을 최대화해야 한다.

입력

각 테스트는 여러 테스트 케이스로 이루어진다. 첫 번째 줄에는 테스트 케이스의 개수인 정수 $t$ ($1\le t\le100\,000$) 하나가 주어진다. 다음 $2t$줄에는 테스트 케이스들의 설명이 주어진다.

각 테스트 케이스의 첫 번째 줄에는 순열의 크기인 정수 $n$ ($2\le n\le200\,000$) 하나가 주어진다.

각 테스트 케이스의 두 번째 줄에는 원래 순열인 $n$개의 정수 $p_1,p_2,\ldots,p_n$이 주어진다. $p$의 원소 중 $1$부터 $n$까지의 각 수가 정확히 한 번씩 나타남이 보장된다.

모든 테스트 케이스에 대한 $n$의 합은 $200\,000$을 넘지 않는다.

출력

각 테스트 케이스마다 정수 하나를 출력하라. 최적으로 나누었을 때 가능한 $q$의 최고 기록 개수와 $r$의 최저 기록 개수의 합의 최댓값이다.

서브태스크

한 테스트에 포함된 모든 테스트 케이스의 $n$값의 합을 $N$이라고 하자.

예제

입력 1

4
5
4 1 2 3 5
10
3 8 10 4 1 2 7 9 5 6
3
1 2 3
6
4 2 5 1 6 3

출력 1

5
6
3
5

참고

첫 번째 테스트 케이스에서 $p$를 $q$와 $r$로 최적으로 나누는 방법 중 하나는 다음과 같다. $q$의 최고 기록과 $r$의 최저 기록은 테두리로 표시하였다:

• $q=\boxed{1}\ \boxed{2}\ \boxed{3}\ \boxed{5}$
• $r=\boxed{4}$

두 번째 테스트 케이스에서 $p$를 $q$와 $r$로 최적으로 나누는 방법 중 하나는 다음과 같다:

• $q=\boxed{3}\ \boxed{8}\ 4\ 1\ 2\ \boxed{9}$
• $r=\boxed{10}\ \boxed{7}\ \boxed{5}\ 6$