CF1905D.Cyclic MEX

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).

对于一个数组 $a$，定义其代价为 $\sum_{i=1}^{n} \operatorname{mex} ^\dagger ([a_1,a_2,\ldots,a_i])$。

给定集合 $\{0,1,2,\ldots,n-1\}$ 的一个排列$^\ddagger$ $p$。求 $p$ 的所有循环移位中所能达到的最大代价。

$^\dagger\operatorname{mex}([b_1,b_2,\ldots,b_m])$ 是最小的非负整数 $x$，使得 $x$ 不在 $b_1,b_2,\ldots,b_m$ 中出现。

$^\ddagger$ 集合 $\{0,1,2,...,n-1\}$ 的一个排列是指由 $0$ 到 $n-1$ 中互不相同的 $n$ 个整数以任意顺序组成的数组。例如，$[1,2,0,4,3]$ 是一个排列，但 $[0,1,1]$ 不是排列（数字 $1$ 在数组中出现了两次），$[0,2,3]$ 也不是排列（此时 $n=3$，但数组中出现了 $3$）。

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 \lt n$) — the elements of the permutation $p$.

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

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。随后是各测试用例的描述。

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

每个测试用例的第二行包含 $n$ 个互不相同的整数 $p_1, p_2, \ldots, p_n$（$0 \le p_i \lt n$），即排列 $p$ 的元素。

保证所有测试用例的 $n$ 值之和不超过 $10^6$。

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

对于每个测试用例，输出一个整数——即 $p$ 的所有循环移位中最大的代价。

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$.

在第一个测试用例中，获得最大开销的循环移位是 $[2,1,0,5,4,3]$，其开销为 $0+0+3+3+3+6=15$。

在第二个测试用例中，获得最大开销的循环移位是 $[0,2,1]$，其开销为 $1+1+3=5$。