Background

Original link: https://oier.team/problems/S3A。

Problem Description

Given a permutation $p$ of $1 \sim n$, ask how many indices $i$ ($1 \le i < n$) satisfy that after sorting, both $[p_1,p_2,\cdots,p_i]$ and $[p_{i+1},p_{i+2},\cdots,p_n]$ are arithmetic progressions.

Input Format

This problem contains multiple test cases in a single test file.

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

Then for each test case, the format is:

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

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

Output Format

For each test case, output one line containing one integer, the answer to the query.

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

3
3

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

2
5
2
0

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

1
1
4
5
1
4

Hint

[Sample Explanation #1]

Test case 1: There are three splits: $[1,3,2][4]$, $[1,3][2,4]$, $[1][3,2,4]$.

Test case 2: There are three splits: $[1][5,3,2,4]$, $[1,5][3,2,4]$, $[1,5,3][2,4]$.

[Sample Explanation #2]

Test case 1: There are two splits: $[2,1][4,3,6,5]$, $[2,1,4,3][6,5]$.

Test case 2: Every split is valid.

Test case 3: Every split is valid.

Test case 4: There is no split, so no split is valid.

[Constraints]

This problem uses bundled tests.

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

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$. It is guaranteed that $p$ is a permutation and $1 \le p_i \le n$.

Please use fast input/output.

A new subtask 4 is added as hack testdata, with a score of $\boldsymbol{0}$.

Translated by ChatGPT 5