Records and anti-records

A permutation of size $n$ is a sequence of integers $a_1, a_2, \ldots, a_n$ in which every value from $1$ to $n$ appears exactly once.

A sequence $b_1, b_2, \ldots, b_l$ is a subsequence of $a_1, a_2, \ldots, a_n$ if it can be obtained by deleting some elements of $a$. That is, $l \le n$ and there exist indices $i_1 < i_2 < \ldots < i_l$ with $a_{i_t} = b_t$.

• An element $a_i$ is a record if it is strictly greater than all previous elements, that is, $a_j < a_i$ for all $1 \le j < i$.
• An element $a_i$ is an anti-record if it is strictly less than all previous elements, that is, $a_j > a_i$ for all $1 \le j < i$.

You are given a permutation $p_1, p_2, \ldots, p_n$. Split $p$ into two non-empty subsequences $q$ and $r$. Every element of $p$ must belong to exactly one of them. Maximize the sum of the number of records in $q$ and the number of anti-records in $r$.

The first line contains a single integer $t$ ($1 \le t \le 100\,000$), the number of test cases. Each test case consists of two lines.

The first line contains a single integer $n$ ($2 \le n \le 200\,000$), the size of the permutation. The second line contains $n$ integers $p_1, p_2, \ldots, p_n$. Each number from $1$ to $n$ appears exactly once.

The sum of $n$ over all test cases does not exceed $200\,000$.

For each test case, print one integer on a separate line: the maximum possible sum of the number of records in $q$ and the number of anti-records in $r$ over an optimal split.

In the first test case, one optimal split is shown below. Boxed elements are the records in $q$ and the anti-records in $r$.

• $q = \boxed{1}\ \boxed{2}\ \boxed{3}\ \boxed{5}$
• $r = \boxed{4}$

In the second test case, one optimal split is shown below.

• $q = \boxed{3}\ \boxed{8}\ 4\ 1\ 2\ \boxed{9}$
• $r = \boxed{10}\ \boxed{7}\ \boxed{5}\ 6$