Для массива \(a\) определим его стоимость как \(\sum_{i=1}^{n} \operatorname{mex} ^\dagger ([a_1,a_2,\ldots,a_i])\).
Вам дана перестановка\(^\ddagger\) \(p\) множества \(\{0,1,2,\ldots,n-1\}\). Найдите максимальную стоимость среди всех циклических сдвигов \(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\}\) является массив, состоящий из \(n\) различных целых чисел от \(0\) до \(n-1\) в произвольном порядке. Например, \([1,2,0,4,3]\) — перестановка, но \([0,1,1]\) не перестановка (\(1\) встречается дважды в массиве), и \([0,2,3]\) тоже не перестановка (\(n=3\), но есть \(3\) в массиве).
Примечание
В первом наборе входных данных циклическим сдвигом, дающим максимальную стоимость, является \([2,1,0,5,4,3]\) со стоимостью \(0+0+3+3+3+6=15\).
Во втором наборе входных данных циклическим сдвигом, дающим максимальную стоимость, является \([0,2,1]\) со стоимостью \(1+1+3=5\).