题目背景

野心 - 薛之谦

题目描述

给出一个 $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

样例 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]$。

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

样例 2 解释

第一组：两种拆分为 $[2,1][4,3,6,5]$，$[2,1,4,3][6,5]$。

第二组：每种拆分都是合法的。

第三组：每种拆分都是合法的。

第四组：不存在拆分方案，故没有方案合法。

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

数据范围

本题开启捆绑测试。

设 $\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$。

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

新增两组 hack 数据，因 OJ 限制，这些数据放在子任务 3。