【MX-S3-T1】「FeOI Round 1」野心


给出一个 $1 \sim n$ 的排列 $p$，询问存在多少个数 $i$（$1 \le i <n$）满足 $[p_1,p_2,\cdots,p_i]$ 和 $[p_{i+1},p_{i+2},\cdots,p_n]$ 排序后都是等差数列。

**本题单个测试点内包含多组数据。** 第一行一个整数 $T$ 表示数据组数。 接下来，对于每组数据，格式如下： 第一行一个数 $n$ 表示排列长度。 接下来一行 $n$ 个数表示排列 $p$。

对于每组测试数据，输出一行一个数表示询问的答案。

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

**【样例解释 #1】** 第一组：三种拆分为 $[1,3,2][4]$，$[1,3][2,4]$，$[1][3,2,4]$。 第二组：三种拆分为 $[1][5,3,2,4]$，$[1,5][3,2,4]$，$[1,5,3][2,4]$。 **【样例解释 #2】** 第一组：两种拆分为 $[2,1][4,3,6,5]$，$[2,1,4,3][6,5]$。 第二组：每种拆分都是合法的。 第三组：每种拆分都是合法的。 第四组：不存在拆分方案，故没有方案合法。 **【数据范围】** **本题开启捆绑测试。** 设 $\sum n$ 为单个测试点内所有的 $n$ 之和。 对于 $100\%$ 的数据，$1 \le T \le 10^5$，$1 \le n \le 10^6$，$1 \le \sum n \le 2 \times 10^6$，保证 $p$ 是排列且 $1 \le p_i \le n$。 | 子任务编号 | $n $ | $\sum n $ | 分数 | | :-: | :-: | :-: | :-: | | $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$ | **请使用较快的输入输出方式。** **新增子任务 4 为 hack 数据，分值为 $\boldsymbol{0}$。**