问题分析

本题要求我们找到一个排列 p 中的所有“好数组”区间的个数。具体来说，给定一个排列 p 和多个查询，每个查询包含一个长度为奇数的区间 [l, r]，并要求判断区间内的中位数是否满足“好数组”的条件：该区间的中位数恰好是区间的第 (r - l + 1) // 2 + 1 的位置上的数字，并且此中位数在该区间内不需要进行排序后也符合中位数的定义。

“好数组”的定义

“好数组”要求数组的中位数即为该区间的第 (n + 1) / 2 个元素（即中间元素）。例如，若数组的长度为 5，那么第 3 个元素就是中位数。

解题思路

题目内容

众所周知，一个长度为$n$，$n$为奇数的数组的中位数是其排序后下标为$\frac{n+1}{2}$的数字。

但小美发现，有些长为奇数n的数组即使不排序，其下标为$\frac{n+1}{2}$的数字依然是其数组中位数，他将满足这样性质的数组成为“好数组"。

现在小美有一个长度为$n$的排列$p$，他想知道$p$中有多少个连续的区间组成的数组都是"好数组"。

(即有多少对$l,r(1≤l≤r≤n)$,同时$r-l+1$是奇数,满足$P_l,P_{l+1},··,P_r$是一个好数组。)

输入描述

每个测试文件内都包含多组测试数据。

第一行一个正整数$T(I≤T≤1000)$，表示测试数据的组数。

接下来对于每组测试数据，输入包含两行。

第一行两个整数$n(1≤n≤10000)$，表示排列$p$的长度。

第二行$n$个整数$p_i(1≤p_i≤n)$，表示排列$P$。

(保证输入是一个排列。)

(保证所有测试数据中$n$的总和不超过$10000$)

输出描述

输出包含 $T$行，每行一个正整数，表示合法的$l,r$对数。

样例1

输入

1
5
3 2 1 4 5

输出

7

说明

好数组的区间有: $[1, 1]$, $[2, 2]$, $[3,3]$, $[4,4]$, $[5,5]$, $[1, 3]$, $[3,5]$这 $7$个。