对于数组 $$$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$$$。