L. MEX 子数组
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

给定一个由 $$$0∼n−1$$$ 组成的排列$$$^{\text{∗}}$$$ $$$p$$$，请求出对于排列 $$$p$$$ 所有非空子数组$$$^{\text{†}}$$$ $$$b$$$ 的 $$$\operatorname{MEX}$$$$$$^{\text{‡}}$$$ 值总和。

$$$^{\text{∗}}$$$ 排列：对于一个 $$$0∼n−1$$$ 排列，排列中仅有恰好一个整数 $$$x\in [0,n−1]$$$。例如：

  • $$$[1,0,2,3]$$$ 是一个排列。
  • $$$[1,1,2,0]$$$ 不是一个排列，因为 $$$1$$$ 出现了超过一次。
  • $$$[0,3,1,4]$$$ 不是一个排列，因为 $$$2$$$ 没有出现。

$$$^{\text{†}}$$$对于一个长度为 $$$m$$$ 的数组 $$$c$$$，选择 $$$2$$$ 个正整数 $$$1\le l\le r\le m$$$，则所有取出下标为 $$$l\le i\le r$$$ 的元素 $$$c_i$$$，并按原顺序排列组成的序列，则叫数组 $$$c$$$ 的子数组。其中区间长度不为 $$$0$$$ 的子数组，为非空子数组。

$$$^{\text{‡}}$$$ $$$\operatorname{MEX}$$$：对于序列 $$$a$$$，它的 $$$\operatorname{MEX}$$$ 值表示最小未出现的自然数。例如：

  • $$$[1,2,0]$$$ 的 $$$\operatorname{MEX}$$$ 值为 $$$3$$$，因为 $$$3$$$ 是序列中最小未出现的自然数。
  • $$$[1,1,4,5,1,4]$$$ 的 $$$\operatorname{MEX}$$$ 值为 $$$0$$$。
  • $$$[0,1,2,5,5,4]$$$ 的 $$$\operatorname{MEX}$$$ 值为 $$$3$$$。
Input

第一行输入一个正整数 $$$T\ (1\le T\le 10^4)$$$，表示测试组数。

接下来每组测试数据，第一行输入一个正整数 $$$n\ (1\le n\le 10^6)$$$，表示排列长度。

第二行输入 $$$n$$$ 个非负整数 $$$a_i\ (0\le a_i\lt n)$$$，表示 $$$0\sim n-1$$$ 的排列。

数据保证所有测试组 $$$n$$$ 的总和不超过 $$$10^6$$$。

Output

对于每组数据，输出一个整数，表示答案。

Example
Input
9
5
2 4 1 0 3
4
1 0 2 3
6
5 1 2 4 0 3
6
1 0 5 4 3 2
10
8 5 3 1 9 0 6 4 2 7
9
2 7 6 3 0 8 1 4 5
10
1 8 6 5 7 3 4 2 0 9
12
11 0 7 4 5 8 10 9 3 2 6 1
15
1 12 0 14 3 9 8 4 13 6 7 10 11 2 5
Output
18
12
23
19
82
52
35
43
68
Note

对于第二组数据，所有连续子数组的 $$$\text{mex}$$$ 值计算如下：

  • 长度为 $$$4$$$：$$$\text{mex}([1, 0, 2, 3]) = 4$$$
  • 长度为 $$$3$$$：$$$\text{mex}([1, 0, 2]) = 3$$$，$$$\text{mex}([0, 2, 3]) = 1$$$
  • 长度为 $$$2$$$：$$$\text{mex}([1, 0]) = 2$$$，$$$\text{mex}([0, 2]) = 1$$$，$$$\text{mex}([2, 3]) = 0$$$
  • 长度为 $$$1$$$：$$$\text{mex}([1]) = 0$$$，$$$\text{mex}([0]) = 1$$$，$$$\text{mex}([2]) = 0$$$，$$$\text{mex}([3]) = 0$$$
将上述所有结果相加：$$$4 + 3 + 1 + 2 + 1 + 0 + 0 + 1 + 0 + 0 = 12$$$。