D. Cyclic MEX
data structures; implementation; math; two pointers
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).
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\).
For each test case, output a single integer — the maximum cost across all cyclic shifts of \(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\).