D. Циклический MEX
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для массива $$$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$$$ в массиве).

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$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$$$.

Пример
Входные данные
4
6
5 4 3 2 1 0
3
2 1 0
8
2 3 6 7 0 1 4 5
1
0
Выходные данные
15
5
31
1
Примечание

В первом наборе входных данных циклическим сдвигом, дающим максимальную стоимость, является $$$[2,1,0,5,4,3]$$$ со стоимостью $$$0+0+3+3+3+6=15$$$.

Во втором наборе входных данных циклическим сдвигом, дающим максимальную стоимость, является $$$[0,2,1]$$$ со стоимостью $$$1+1+3=5$$$.