### 问题描述 小桥是一个聪明的数学家，他喜欢研究数列的性质。最近，他在研究一类特殊的数列，即长度为 $n$，由 $0, 1, \dots, n-1$ 这 $n$ 个数字组成的排列。 他定义了两个函数 $med(S)$ 和 $mex(S)$，其中 $S$ 是一个由 $n$ 个数字组成的特殊的序列。 $med(S)$ 表示将 $S$ 中的数字从小到大排序后，位于中间位置的数的值，如果有多个中间位置，则取最靠左边的那个。例如，$med(0, 1, 2, 3) = 1$，$med(0, 4, 1, 3) = 1$，$med(5, 4, 0, 1, 2) = 2$。 而 $mex(S)$ 表示 $S$ 中没有出现的最小非负整数。例如，$mex(0, 1, 2, 3) = 4$，$mex(0, 4, 1, 3) = 2$，$mex(5, 4, 0, 1, 2) = 3$。 小桥现在想研究这种排列中一些特殊的子段，即满足 $mex(p_l, p_{l+1}, \dots, p_r) > med(p_l, p_{l+1}, \dots, p_r)$ 的所有子段 $[l, r]$ 的个数。 他想求出这个所有特殊子段的个数，希望你能帮帮他。 ### 输入格式 第一行包含一个整数 $t$，表示测试数据的组数。 每组测试数据包含两行，第一行包含一个整数 $n$，表示排列的长度。 第二行包含 $n$ 个非负整数，表示排列中的数。 ### 输出格式 对于每组测试数据，输出一个整数，表示满足条件的子段的个数。 ### 样例输入 ```txt 8 1 0 2 1 0 3 1 0 2 4 0 2 1 3 5 3 1 0 2 4 6 2 0 4 1 3 5 8 3 7 2 6 0 1 5 4 4 2 0 1 3 ``` ### 样例输出 ```txt 1 2 4 4 8 8 15 6 ``` ### 样例说明 第一个测试用例仅包含一个子段，其 $mex({0}) = 1 > med({0}) = 0$。 在第三个测试用例中，以下子段满足条件：$[1,0]$，$[0]$，$[1,0,2]$ 和 $[0,2]$，在这些子段中，$mex$ 大于 $med$。 在第四个测试用例中，以下子段满足条件：$[0,2]$，$[0]$，$[0,2,1]$ 和 $[0,2,1,3]$，在这些子段中，$mex$ 大于 $med$。 ### 评测数据规模 对于 $100$% 的评测数据，$1\le t\le 10,1\le n\le 2\cdot 10^5,0\le p_i\le n-1$。