# ROI 23 Records and Anti-Records

https://www.acmicpc.net/problem/28440

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

A sequence $b_1, b_2, \dots, b_l$ is a subsequence of the sequence $a_1, a_2, \dots, a_n$ if $b$ can be obtained from $a$ by deleting some elements (i.e., $l \le n$ and there exist indices $i_1 < i_2 < \ldots < i_l$ such that $a_{i_t} = b_t$).

An element $a_i$ of a sequence is called a record if it is strictly greater than all previous elements (i.e., $a_j < a_i$ for all $1 \le j < i$).

An element $a_i$ of a sequence is called an anti-record if it is strictly less than all previous elements (i.e., $a_j > a_i$ for all $1 \le j < i$).

Given a permutation $p_1, p_2, \dots, p_n$ of size $n$, it is required to split it into two non-empty subsequences $q$ and $r$. In other words, each element of $p$ should belong to exactly one of the subsequences. The goal is to maximize the sum of the number of records in $q$ and the number of anti-records in $r$.

## Input

Each test consists of several sets of input data. The first line contains a single integer $t$ ($1 \le t \le 100,000$) — the number of input sets. The next $2t$ lines contain descriptions of the input sets.

The first line of the description of each input set contains a single integer $n$ — the size of the permutation ($2 \le n \le 200,000$).

The second line of the description of each input set contains $n$ integers $p_1, p_2, \dots, p_n$ — the original permutation. It is guaranteed that each number from $1$ to $n$ appears exactly once among the elements of $p$.

The sum of $n$ for all input sets does not exceed $200,000$.

## Output

For each set of input data, output a single integer — the maximum possible sum of the number of records in $q$ and the number of anti-records in $r$ in the optimal split.
Subtasks

Let $N$ denote the sum of values of $n$ in all input sets of a test.

Subtask 5: the length of the longest decreasing subsequence in $p$ does not exceed 2

## Samples

Example Input 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

Example Output 1

5
6
3
5

### Explanation

One way to optimally split $p$ into $q$ and $r$ for the first set of input data (records in $q$ and anti-records in $r$ are highlighted):

$q = \boxed{1}\ \boxed{2}\ \boxed{3}\ \boxed{5}$

$r = \boxed{4}$

One way to optimally split $p$ into $q$ and $r$ for the second set of input data:

$q = \boxed{3}\ \boxed{8}\ 4\ 1\ 2\ \boxed{9}$

$r = \boxed{10}\ \boxed{7}\ \boxed{5}\ 6$