CF1905D Cyclic MEX

对于一个数组 $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])$ 表示最小的不在 $b_1,b_2,\ldots,b_m$ 中出现的非负整数 $x$。 $^\ddagger$ 集合 $\{0,1,2,...,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$（$1 \le n \le 10^6$），表示排列 $p$ 的长度。 每个测试用例的第二行包含 $n$ 个互不相同的整数 $p_1, p_2, \ldots, p_n$（$0 \le p_i < n$），表示排列 $p$ 的元素。 保证所有测试用例中 $n$ 的总和不超过 $10^6$。

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

在第一个测试用例中，能获得最大代价的循环移位为 $[2,1,0,5,4,3]$，其代价为 $0+0+3+3+3+6=15$。 在第二个测试用例中，能获得最大代价的循环移位为 $[0,2,1]$，其代价为 $1+1+3=5$。 由 ChatGPT 4.1 翻译