#924 Skyline

Statement

Statement language

There are buildings with heights $A_1,A_2,\cdots,A_N$ placed in order from the left. The $i$ -th building from the left is called building $i$ .

Building $X$ is said to be central if it satisfies both of the following conditions.

For all $i$ such that ( $1 \leq i<X$ ), $A_i \leq A_X$ .

If there is no building in the corresponding range, that condition is considered to be satisfied. In the figure above, buildings $3$ , $4$ , $7$ , and $8$ , marked in blue, are the central buildings.

Find the number of central buildings.

Input

The input is given in the following format.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print the number of central buildings on a single line.

Constraints

$1 \leq T \leq 100\,000$ .
$1 \leq N \leq 200\,000$ .
$1 \leq_{}$ ().

Subtasks

#	Score	Constraints
1	25	$N\leq100$ , $\sum N\leq1000$ .
2	75	No additional constraints.

Samples

Input

3
8
2 1 3 3 5 4 6 7
5
3 3 3 3 3
3
3 2 1

Output

4
5
0