P11106 [ROI 2023] Peaks (Day 1)

Translated from [ROI 2023 D1T3](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-roi-2023-day1.pdf)。 If for all $1 \le j < i$, we have $a_j < a_i$, then $a_i$ is called a peak. If for all $1 \le j < i$, we have $a_j > a_i$, then $a_i$ is called an anti-peak.

You are given a permutation $p_1,p_2,\dots,p_n$ of size $n$. You need to split it into two non-empty subsequences $q$ and $r$. Each element of $p$ must be assigned to exactly one subsequence. You need to maximize the sum of the number of peaks in $q$ and the number of anti-peaks in $r$.

Each test consists of multiple test cases. The first line contains an integer $t(1 \le t \le 100,000)$, the number of test cases. The next $2t$ lines describe the test cases, with each test case given in two lines. The first line of each test case contains an integer $n(2 \le n \le 200,000)$, the size of the permutation. The second line of each input test case contains $n$ integers $p_1,p_2,\dots,p_n$, the original permutation. It is guaranteed that each number appears exactly once in $p$. The sum of $n$ over all test cases does not exceed $200,000$.

For each test case, output one integer: the maximum possible value of the number of peaks in $q$ plus the number of anti-peaks in $r$ after splitting $p$.

Explanation of the first two samples:  Let $N=\sum n$. | Subtask | Score | $n,N$ | Special Properties | | :----------: | :----------: | :----------: | :----------: | | $1$ | $21$ | $n\le16$ | $t\le120$ | | $2$ | $22$ | $n\le200,N\le2000$ | | | $3$ | $14$ | $N\le2000$ | | | $4$ | $10$ | $N\le20000$ | | | $5$ | $13$ | $N\le200000$ | The length of the longest decreasing subsequence of $p$ is at most $2$ | | $6$ | $20$ | $N\le200000$ | | Translated by ChatGPT 5