D. 循环 MEX

对于一个数组 $a$，定义它的代价为：

$$\sum_{i=1}^{n} \operatorname{mex}([a_1,a_2,\dots,a_i]) $$

给定集合 $\{0,1,2,\dots,n-1\}$ 的一个排列 $p$。你需要求出 $p$ 的所有循环移位中，代价的最大值。

$\operatorname{mex}([b_1,b_2,\dots,b_m])$ 表示最小的非负整数 $x$，使得 $x$ 没有在 $b_1,b_2,\dots,b_m$ 中出现。

集合 $\{0,1,2,\dots,n-1\}$ 的一个排列，是一个长度为 $n$ 的数组，其中恰好包含从 $0$ 到 $n-1$ 的所有整数且互不相同，顺序任意。例如，$[1,2,0,4,3]$ 是一个排列，但 $[0,1,1]$ 不是排列，因为 $1$ 出现了两次；$[0,2,3]$ 也不是排列，因为此时 $n=3$，但数组中出现了 $3$。

输入格式

每个输入包含多组测试数据。

第一行包含一个整数 $t$，表示测试数据组数，其中：

$$1 \le t \le 10^5$$

对于每组测试数据：

第一行包含一个整数 $n$，表示排列 $p$ 的长度，其中：

$$1 \le n \le 10^6$$

第二行包含 $n$ 个互不相同的整数 $p_1,p_2,\dots,p_n$，表示排列 $p$ 的元素，其中：

$$0 \le p_i < n$$

保证所有测试数据中 $n$ 的总和不超过：

$$10^6$$

输出格式

对于每组测试数据，输出一个整数，表示所有循环移位中代价的最大值。

样例输入

4
6
5 4 3 2 1 0
3
2 1 0
8
2 3 6 7 0 1 4 5
1
0

样例输出

15
5
31
1

说明

在第 $1$ 组测试数据中，使代价最大的循环移位为 $[2,1,0,5,4,3]$，其代价为：

$$0+0+3+3+3+6=15$$

在第 $2$ 组测试数据中，使代价最大的循环移位为 $[0,2,1]$，其代价为：

$$1+1+3=5$$