404527: GYM101532 G Magical Indices

Memory Limit:256 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. Magical Indicestime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Alaa sometimes feels bored at work, so at such times she starts playing with a beautiful array a consisting of n integers a1, a2, ..., an.

Alaa starts counting the number of magical indices in the array a. An index x is said to be magical if it satisfying the following rules:

  1. 1 < x < n
  2. ay ≤ ax, for each y (1 ≤ y < x).
  3. ax ≤ az, for each z (x < z ≤ n).

Can you help Alaa by counting the number of magical indices in the array a.

Input

The first line contains an integer T, where T is the number of test cases.

The first line of each test case contains an integer n (1 ≤ n ≤ 106), where n is the size of the array a.

The second line of each test case contains n integers a1, a2, ..., an (1 ≤ ai ≤ 106), giving the array a.

Output

For each test case, print a single line containing the number of magical indices in the array a.

ExampleInput
2
8
2 1 3 4 6 5 7 9
6
4 2 7 9 8 10
Output
3
1
Note

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.

加入题单

上一题 下一题 算法标签: