思路

排列其实就是一个数组$n$个数，包好$1$到$n$各一位。所以我们可以将数组排序，将数组排序后，我们会得到一个$1$到$n$的数组，同时我们用$pos[i]$表示一个数$i$在原数组的位置。

我们拿样例$[2,1,5,3,4]$来讲解。

那么我们得到的$pos$数组是$[2,1,4,5,3]$。

我们将数字和$pos$绑定为二元组。所以原数组为$[(2,1),(1,2),(5,3),(3,4),(4,5)]$（二元组第一位表示数字，第二位表示位置）。我们排序后，数组变为$[(1,2),(2,1),(3,4),(4,5),(5,3)]$。

题目内容

魔法师小红手上有一个长度为 $n$ 的序列 $a_1, a_2, \ldots, a_n$，保证序列里每个元素不重复且$1 <= a[i] <= n$，他想要知道有多少个区间 $[l, r]$ 满足区间内部的数 $a_{l}, a_{l+1}, \ldots, a_{r}$ 能够构成一个排列。

为了更好地掌握魔法，小红需要知道所有满足条件的区间数量。现在他请你来帮助他计算这个数量。

排列的定义： $1$ 到 $k$ ，每个数都出现过且恰好出现 $1$ 次，被称为一个长度为 $k$ 的排列。

例如 $[2,1,3]$ ， $[4,3,2,1]$ 都是排列。

输入描述

有多组数据，首先输入一个正整数 $T$ ，表示有 $T$ 组数据。

每组数据的第一行输入一个正整数 $n$ ，代表排列的大小。

每组数据的第二行输入个 $n$ 正整数 $a_i$ ，代表小红拿到的排列。

$1\le T\le 2$ ，且对于90%的用例，$T=1，1 \le n \le 2 \times 10^5$

保证所有数据 $n$ 的总和不超过 $2\times 10^5$ 。

输出描述

输出一个整数，代表多少区间能构成一个排列。

样例

输入

3
3
3 1 2
5
5 3 1 4 2
7
1 2 3 4 5 6 7

输出

3
3
7