P10885 [MX-S3-T1] "FeOI Round 1" Ambition.

Original link: 。 --- 

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.

**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$.

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

**[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$. | Subtask ID | $n$ | $\sum n$ | Score | | :-: | :-: | :-: | :-: | | $1$ | $\le 10^3$ | $\le 5\times 10^3$ | $30$ | | $2$ | $\le 10^5$ | $\le 5\times 10^5$ | $30$ | | $3$ | $\le 10^6$ | $\le 2\times 10^6$ | $40$ | **Please use fast input/output.** **A new subtask 4 is added as hack testdata, with a score of $\boldsymbol{0}$.** Translated by ChatGPT 5