Background

Translated from ROI 2023 D1T3。

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.

Problem Description

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$.

Input Format

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$.

Output Format

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$.

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

Hint

Explanation of the first two samples:

Let $N=\sum n$.

Translated by ChatGPT 5