← 返回题目列表

Codeforces · 1905/D

D. 循环 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])$$$ 是最小的非负整数 $$$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$$$)。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$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$$$。

输出

对于每个测试用例,输出一个整数 - $$$p$$$ 的所有循环移位的最大成本。

示例

输入 #1

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

输出 #1

15
5
31
1

注意

在第一个测试用例中,产生最大成本的循环移位为 $$$[2,1,0,5,4,3]$$$,成本为 $$$0+0+3+3+3+6=15$$$。

在第二个测试用例中,产生最大成本的循环移位是 $$$[0,2,1]$$$,成本为 $$$1+1+3=5$$$。