Problem Description

Given a permutation $p$ of numbers from $1$ to $n$, query how many numbers $i$ (where $1 \le i < n$) exist such that both $[p_1, p_2, \cdots, p_i]$ and $[p_{i+1}, p_{i+2}, \cdots, p_n]$ sorted are arithmetic sequences.

Input Format

This problem contains multiple test cases within a single test point.

The first line contains an integer $T$ representing the number of test cases.

For each test case, the format is as follows:

The first line contains an integer $n$ representing the length of the permutation.

The next line contains $n$ integers representing the permutation $p$.

Output Format

For each test case, output a single line containing an integer representing the answer to the query.

Sample Input and Output

Sample Input #1

2
4
1 3 2 4
5
1 5 3 2 4

Sample Output #1

3
3

Sample Input #2

4
6
2 1 4 3 6 5
6
1 2 3 4 5 6
3
1 3 2
1
1

Sample Output #2

2
5
2
0

Sample Input #3

6
2
1 2
20
16 2 10 18 4 6 8 20 14 12 3 9 17 13 1 15 7 11 19 5
9
3 4 1 5 2 6 7 8 9
10
1 3 2 4 7 6 5 8 10 9
13
5 7 3 11 1 9 13 6 10 4 2 8 12
5
1 2 3 4 5

Sample Output #3

1
1
4
5
1
4

Notes

[Sample Explanation #1]

First group: The three partitions are $[1,3,2][4]$, $[1,3][2,4]$, and $[1][3,2,4]$.

Second group: The three partitions are $[1][5,3,2,4]$, $[1,5][3,2,4]$, and $[1,5,3][2,4]$.

[Sample Explanation #2]

First group: The two partitions are $[2,1][4,3,6,5]$ and $[2,1,4,3][6,5]$.

Second group: Every partition is valid.

Third group: Every partition is valid.

Fourth group: No partition scheme exists, hence no valid schemes.

[Data Range]

This problem has subtask testing enabled.

Let $\sum n$ be the sum of all $n$ within a single test point.

For $100\%$ of the data, $1 \le T \le 10^5$, $1 \le n \le 10^6$, $1 \le \sum n \le 2 \times 10^6$, and $p$ is a permutation with $1 \le p_i \le n$.

Please use fast input and output methods.

A new subtask 4 for hack data has been added, worth $\boldsymbol{0}$ points.

见题面 Input 部分

见题面 Output 部分