CF1905D Cyclic MEX

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 $ .