#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

Big Pick - Repovive Starter Round 7 | Repovive

21E. Big Pick

2500 pts2s256 MB

There are $n$ cards arranged in a row. The number written on the $i$ -th card is $p_i$ , and $p$ is a permutation of $1,2,\ldots,n$ .

In one operation, you remove either the leftmost or the rightmost remaining card. If the removed card is the largest card remaining immediately before the operation, you gain one point.

You continue until all cards have been removed. Find the maximum score you can obtain.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$p$ is a permutation of $1,2,\ldots,n$
The sum of $n$ over all test cases does not exceed $2 \times 10^5$

Input

t

\left. \begin{array}{l} n \\ p_1 \quad p_2 \quad \cdots \quad p_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

5
5 1 4 2 3

Case 2

5
1 2 3 4 5

Explanation

Case 1

Remove $5$ , $1$ , and $4$ from the left, then remove $3$ and $2$ from the right. Every removal except that of card $1$ gives one point. It is impossible to score on all five removals because, after card $5$ is removed, the largest remaining card is not at either end.

Case 2

Remove every card from the right. Each removed card is the largest one remaining, so the final score is $5$ .

Output

Case 1

Case 2

Input

Case 1

1
1

Case 2

7
5 6 4 7 2 3 1

Case 3

6
6 4 2 1 3 5

Explanation

Case 1

The only card is also the largest remaining card, so removing it gives one point.

Case 2

One optimal choice is to remove $1$ , $3$ , and $2$ from the right, followed by $7$ , $5$ , $6$ , and $4$ . The removals of $7$ , $6$ , and $4$ give points. No better score is possible: before removing $7$ , one whole side of it must disappear, and the largest card on either side initially lies between two other cards.

Case 3

Remove cards alternately from the left and the right in the order $6,5,4,3,2,1$ . Every removed card is the largest remaining card, giving a score of $6$ .

Output

Case 1

Case 2

Case 3

There are $n$ cards arranged in a row. The number written on the $i$ -th card is $p_i$ , and $p$ is a permutation of $1,2,\ldots,n$ .

In one operation, you remove either the leftmost or the rightmost remaining card. If the removed card is the largest card remaining immediately before the operation, you gain one point.

You continue until all cards have been removed. Find the maximum score you can obtain.

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$p$ is a permutation of $1,2,\ldots,n$
The sum of $n$ over all test cases does not exceed $2 \times 10^5$

t

\left. \begin{array}{l} n \\ p_1 \quad p_2 \quad \cdots \quad p_n \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

Remove every card from the right. Each removed card is the largest one remaining, so the final score is $5$ .

Remove cards alternately from the left and the right in the order $6,5,4,3,2,1$ . Every removed card is the largest remaining card, giving a score of $6$ .

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

21E. Big Pick

Constraints

Input

Output

Samples

21E. Big Pick

Constraints

Input

Output

Samples