题目背景

题目描述

给出一个 $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$
$3$	$\le 10^6$	$\le 2\times 10^6$	$40$

请使用较快的输入输出方式。

新增子任务 4 为 hack 数据，分值为 $\boldsymbol{0}$。