题目内容

魔法师塔子哥手上有一个长度为 $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