D. Cyclic MEXtime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputFor 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.^\ddaggerA 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).InputEach 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.OutputFor each test case, output a single integer — the maximum cost across all cyclic shifts of p.ExampleInput
465 4 3 2 1 032 1 082 3 6 7 0 1 4 510Output
15
5
31
1
NoteIn 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.
465 4 3 2 1 032 1 082 3 6 7 0 1 4 510
15 5 31 1 
['data structures', 'implementation', 'math', 'two pointers', '*2000']