레코드와 안티레코드

시간 제한3초메모리 제한1024 MB

요약

순열을 공집합이 아닌 두 부분수열로 나눠, 첫 번째 수열의 기록 개수와 두 번째 수열의 역기록 개수 합의 최댓값을 구합니다.

문제

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

수열 $b_1, b_2, \ldots, b_l$ 은 $a$ 에서 일부 원소를 지워서 얻을 수 있으면 $a$ 의 부분수열이다. 즉 $l \le n$ 이고, $a_{i_t} = b_t$ 를 만족하는 인덱스 $i_1 < i_2 < \ldots < i_l$ 이 존재한다.

원소 $a_i$ 가 자신보다 앞에 있는 모든 원소보다 엄격히 크면 레코드이다. 즉 $1 \le j < i$ 인 모든 $j$ 에 대해 $a_j < a_i$ 이다.
원소 $a_i$ 가 자신보다 앞에 있는 모든 원소보다 엄격히 작으면 안티레코드이다. 즉 $1 \le j < i$ 인 모든 $j$ 에 대해 $a_j > a_i$ 이다.

순열 $p_1, p_2, \ldots, p_n$ 이 주어진다. $p$ 를 비어 있지 않은 두 부분수열 $q$ 와 $r$ 로 나눈다. $p$ 의 각 원소는 둘 중 정확히 하나에 속한다. $q$ 의 레코드 개수와 $r$ 의 안티레코드 개수의 합을 최대화한다.

첫 줄에 테스트 케이스의 수 $t$ ( $1 \le t \le 100\,000$ )가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다.

첫 줄에는 순열의 크기 $n$ ( $2 \le n \le 200\,000$ )이 주어진다. 둘째 줄에는 순열 $p_1, p_2, \ldots, p_n$ 이 주어진다. $1$ 부터 $n$ 까지의 각 수는 정확히 한 번씩 나타난다.

모든 테스트 케이스의 $n$ 을 합하면 $200\,000$ 을 넘지 않는다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 최적으로 나눴을 때 $q$ 의 레코드 개수와 $r$ 의 안티레코드 개수의 합의 최댓값이다.

첫 번째 테스트 케이스에서 최적으로 나누는 방법 중 하나는 다음과 같다. 박스로 표시한 원소가 $q$ 의 레코드이거나 $r$ 의 안티레코드이다.

두 번째 테스트 케이스에서 최적으로 나누는 방법 중 하나는 다음과 같다.

예제 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

예상 출력