给你一个长度为 $N$ 的正整数数组 $A[1], A[2], \ldots, A[N]$，请问有多少连续的子数组 $A[l..r]$ 满足所构成的序列是合法的 "树序列"，请输出这些子数组的长度总和。
树序列的定义如下：
给定一棵树，所有点都用正整数编号，且相异两点的编号相异，现在任选一点出发，用最少的步数经过所有点后再回到出发点，沿途把经过的点依序写下来，写下的序列就称为 "树序列"。也就是说，一个序列是 "树序列" 当且仅当存在一棵树用上述方法走访完所有点后。途中经过的点的编号依序写下来正好是此序列。
例如："1 2 1", "2", "3 1 3 2 3" 都是 "树序列"，但 "1 2", "1 2 1 2 1" 并不是。
第一行有一个正整数 $T$ ($T \le 10^4$)，代表有几组数据。
接着每组数据的第一行有一个正整数 $N$ ($1 \le N \le 10^6$), 第二行有 $N$ 个正整数代表 $A[1], A[2], \ldots, A[N]$ ($1 \le A[i]\le N$)。
所有的 $N$ 的总和不会超过 $10^6$。
对于每组数据，输出一行包含一个非负整数，代表答案。
4 3 3 2 1 3 1 2 1 5 3 1 3 2 3 7 1 2 3 2 1 2 3
3 6 16 28
以样例的第二组数据作为举例。当 $(l,r) = (1,1), (2,2), (3,3), (1,3)$ 时，A[l..r]都是树序列，子数组长度分别为 $1, 1, 1, 3$，所以长度总和为 $1+1+1+3=6$。当 $(l,r) = (1,2), (2,3)$ 时不是树序列。
Comet OJ