题目内容

考古学家在一处遗迹中发现了一排共 $m$ 个石碑，从左到右编号为 $1$ 到 $m$。每个石碑上都刻有一个正整数。他们想要研究什么叫做“中心石碑”。

对于任意一个不在两端的石碑 $p$（即 $2 \le p \le m-1$），我们可以在它左侧和右侧分别寻找一个参考石碑。

• 左侧参考石碑 $u$：在编号 $1$ 到 $p-1$ 的石碑中，找到数值最大的石碑；如果有多个石碑具有相同的最大值，则选择距离 $p$ 最近的那一个（即编号最大的）。
• 右侧参考石碑 $v$：在编号 $p+1$ 到 $m$ 的石碑中，找到数值最大的石碑；如果有多个石碑具有相同的最大值，则选择距离 $p$ 最近的那一个（即编号最小的）。

如果石碑 $p$ 到左右两个参考石碑的距离相等，即 $p - u = v - p$，我们就称 $p$ 为“中心石碑”。

现在给定这些石碑的数值，请你计算中心石碑的个数。

约束条件

• 测试数据组数 $q$ 满足 $1 \le q \le 10000$。
• 每组石碑数量 $m$ 满足 $3 \le m \le 200000$。
• 单个测试文件中所有组的 $m$ 之和不超过 $200000$。
• 每个石碑上的数值为整数，范围在 $1$ 到 $10^9$ 之间。

输入描述

第一行包含一个整数 $q$，表示测试数据的组数。 接下来依次描述每组测试数据：

1. 第一行包含一个整数 $m$，表示该组石碑的数量。
2. 第二行包含 $m$ 个整数，以空格分隔，依次给出编号 $1$ 到 $m$ 的石碑上的数值。

输出描述

对于每组测试数据，输出一行一个整数，表示该组中“中心石碑”的个数。

样例1

输入

1
3
2 1 2

输出

1

说明

只有中间石碑 $p=2$ 可能成为中心石碑。其左侧石碑只有 1 个，数值为 2，编号为 $1$，因此 $u = 1$。右侧石碑也只有 1 个，数值为 2，编号为 $3$，因此 $v = 3$。计算 $p - u = 2 - 1 = 1$，$v - p = 3 - 2 = 1$，两侧距离均为 $1$，满足中心石碑条件。故中心石碑个数为 1。

样例2

输入

1
5
1 2 3 2 1

输出

3

说明

序列长度为 $m = 5$，石碑数值为 [1, 2, 3, 2, 1]。 考虑 $p = 2, 3, 4$。

• $p = 2$：左侧区间 $[1, 1]$ 最大值为 1，$u = 1$；右侧区间 $[3, 5]$ 最大值为 3，$v = 3$。$2 - 1 = 1$，$3 - 2 = 1$，距离相等。
• $p = 3$：左侧区间 $[1, 2]$ 最大值为 2，$u = 2$；右侧区间 $[4, 5]$ 最大值为 2，距离最近的下标为 $4$，$v = 4$。$3 - 2 = 1$，$4 - 3 = 1$，距离相等。
• $p = 4$：左侧区间 $[1, 3]$ 最大值为 3，$u = 3$；右侧区间 $[5, 5]$ 最大值为 1，$v = 5$。$4 - 3 = 1$，$5 - 4 = 1$，距离相等。 因此 $p = 2, 3, 4$ 均为中心石碑，总数为 3。

样例3

输入

1
6
5 5 1 5 5 1

输出

2

说明

石碑数值为 [5, 5, 1, 5, 5, 1]，$m = 6$。

• $p = 2$：左侧最大值 5 出现在编号 $1$，$u = 1$；右侧最大值 5 出现在编号 $4$ 和 $5$，距 $p$ 最近的为编号 $4$（距离 $4-2=2$），$v = 4$。$2-1=1 eq 2$，不成立。
• $p = 3$：左侧最大值 5 出现在 $1$ 和 $2$，最近为 $2$，$u = 2$；右侧最大值 5 出现在 $4$ 和 $5$，最近为 $4$，$v = 4$。$3-2=1$，$4-3=1$，成立。
• $p = 4$：左侧区间 [1, 3] 最大值为 5，出现在 $1$ 和 $2$，最近为 $2$，$u = 2$；右侧最大值 5 出现在 $5$，$v = 5$。$4-2=2 eq 1$，不成立。
• $p = 5$：左侧区间 [1, 4] 最大值为 5，出现在 $1, 2, 4$，最近为 $4$，$u = 4$；右侧区间 [6, 6] 最大值为 1，$v = 6$。$5-4=1$，$6-5=1$，成立。 中心石碑为 $p = 3$ 和 $p = 5$，总数为 2。