시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB628650.000%

문제

Перестановкой размера $n$ называется последовательность $n$ целых чисел $a_1, a_2, \ldots, a_n$, в которой все значения от $1$ до $n$ встречаются ровно по одному разу.

Последовательность $b_1, b_2, \dots, b_l$ является подпоследовательностью последовательности $a_1, a_2, \dots, a_n$, если $b$ можно получить из $a$ удалением некоторых элементов (то есть $l \le n$ и существуют $i_1 < i_2 < \ldots < i_l$ такие что $a_{i_t} = b_t$).

  • Элемент последовательности $a_i$ называется рекордом, если он строго больше всех предыдущих элементов (то есть $a_j < a_i$ для всех $1 \le j < i$).
  • Элемент последовательности $a_i$ называется антирекордом, если он строго меньше всех предыдущих элементов (то есть $a_j > a_i$ для всех $1 \le j < i$).

Дана перестановка $p_1, p_2, \dots, p_n$ размера $n$. Требуется разделить её на две непустые подпоследовательности $q$ и $r$. Иными словами, каждый элемент $p$ должен попасть ровно в одну из подпоследовательностей. При этом требуется максимизировать сумму количества рекордов в $q$ и количества антирекордов в $r$.

입력

Каждый тест состоит из нескольких наборов входных данных. В первой строке содержится единственное целое число $t$ ($1 \le t \le 100\,000$) --- количество наборов входных данных. В следующих $2t$ строках следуют описания наборов входных данных.

В первой строке описания каждого набора входных данных содержится одно целое число $n$ --- размер перестановки ($2 \le n \le 200\,000$).

Во второй строке описания каждого набора входных данных содержатся $n$ целых чисел $p_1, p_2, \dots, p_n$ --- исходная перестановка. Гарантируется, что среди элементов $p$ каждое число от $1$ до $n$ встречается ровно по одному разу.

Сумма $n$ по всем наборам входных данных не превосходит $200\,000$.

출력

Для каждого набора входных данных выведите одно целое число --- максимальную возможную сумму количества рекордов в $q$ и антирекордов в $r$ в оптимальном разбиении.

서브태스크

Обозначим как $N$ сумму значений $n$ во всех наборах входных данных одного теста.

번호배점제한
121

$n \le 16$, $t \leq 120$

222

$n \le 200$, $N \leq 2000$

314

$N \le 2\,000$

410

$N \le 10\,000$

513

$N \le 200\,000$, Длина наибольшей убывающей подпоследовательности в $p$ не превышает $2$

620

$N \le 200\,000$

예제 입력 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$

채점 및 기타 정보

  • 예제는 채점하지 않는다.