| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 62 | 8 | 6 | 50.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$).
Дана перестановка $p_1, p_2, \dots, p_n$ размера $n$. Требуется разделить её на две непустые подпоследовательности $q$ и $r$. Иными словами, каждый элемент $p$ должен попасть ровно в одну из подпоследовательностей. При этом требуется максимизировать сумму количества рекордов в $q$ и количества антирекордов в $r$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке содержится единственное целое число $t$ (1ドル \le t \le 100,000円$) --- количество наборов входных данных. В следующих 2ドルt$ строках следуют описания наборов входных данных.
В первой строке описания каждого набора входных данных содержится одно целое число $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$ во всех наборах входных данных одного теста.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 21 | $n \le 16,ドル $t \leq 120$ |
| 2 | 22 | $n \le 200,ドル $N \leq 2000$ |
| 3 | 14 | $N \le 2,000円$ |
| 4 | 10 | $N \le 10,000円$ |
| 5 | 13 | $N \le 200,000円,ドル Длина наибольшей убывающей подпоследовательности в $p$ не превышает 2ドル$ |
| 6 | 20 | $N \le 200,000円$ |
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
5 6 3 5
Один из способов оптимальным образом разбить $p$ на $q$ и $r$ в первом наборе входных данных (рекорды в $q$ и антирекорды в $r$ обведены):
Один из способов оптимальным образом разбить $p$ на $q$ и $r$ во втором наборе входных данных: