310889: CF1905D. Cyclic MEX

D. Cyclic MEXtime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

For an array $a$, define its cost as $\sum_{i=1}^{n} \operatorname{mex} ^\dagger ([a_1,a_2,\ldots,a_i])$.

You are given a permutation$^\ddagger$ $p$ of the set $\{0,1,2,\ldots,n-1\}$. Find the maximum cost across all cyclic shifts of $p$.

$^\dagger\operatorname{mex}([b_1,b_2,\ldots,b_m])$ is the smallest non-negative integer $x$ such that $x$ does not occur among $b_1,b_2,\ldots,b_m$.

$^\ddagger$A permutation of the set $\{0,1,2,...,n-1\}$ is an array consisting of $n$ distinct integers from $0$ to $n-1$ in arbitrary order. For example, $[1,2,0,4,3]$ is a permutation, but $[0,1,1]$ is not a permutation ($1$ appears twice in the array), and $[0,2,3]$ is also not a permutation ($n=3$ but there is $3$ in the array).

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^6$) — the length of the permutation $p$.

The second line of each test case contain $n$ distinct integers $p_1, p_2, \ldots, p_n$ ($0 \le p_i < n$) — the elements of the permutation $p$.

It is guaranteed that sum of $n$ over all test cases does not exceed $10^6$.

Output

For each test case, output a single integer — the maximum cost across all cyclic shifts of $p$.

ExampleInput

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

Output

15
5
31
1

Note

In the first test case, the cyclic shift that yields the maximum cost is $[2,1,0,5,4,3]$ with cost $0+0+3+3+3+6=15$.

In the second test case, the cyclic shift that yields the maximum cost is $[0,2,1]$ with cost $1+1+3=5$.

题目大意：
对于一个数组a，定义其cost为 \sum_{i=1}^{n} \operatorname{mex} ([a_1,a_2,\ldots,a_i])。其中，\operatorname{mex}([b_1,b_2,\ldots,b_m]) 表示最小的非负整数x，使得x不在b_1,b_2,\ldots,b_m中。

给定一个由集合{0,1,2,…,n-1}组成的排列p。求p的所有循环移位中的最大cost。

输入数据格式：
第一行包含一个整数t（1≤t≤10^5），表示测试用例的数量。接下来是t个测试用例的描述。

每个测试用例的第一行包含一个整数n（1≤n≤10^6），表示排列p的长度。

每个测试用例的第二行包含n个不同的整数p_1, p_2, …, p_n（0≤p_i
所有测试用例的n之和不超过10^6。

输出数据格式：
对于每个测试用例，输出一个整数，表示p的所有循环移位中的最大cost。题目大意： 对于一个数组a，定义其cost为 \sum_{i=1}^{n} \operatorname{mex} ([a_1,a_2,\ldots,a_i])。其中，\operatorname{mex}([b_1,b_2,\ldots,b_m]) 表示最小的非负整数x，使得x不在b_1,b_2,\ldots,b_m中。 给定一个由集合{0,1,2,…,n-1}组成的排列p。求p的所有循环移位中的最大cost。 输入数据格式： 第一行包含一个整数t（1≤t≤10^5），表示测试用例的数量。接下来是t个测试用例的描述。 每个测试用例的第一行包含一个整数n（1≤n≤10^6），表示排列p的长度。 每个测试用例的第二行包含n个不同的整数p_1, p_2, …, p_n（0≤p_i