Для массива $$$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$$$.
465 4 3 2 1 032 1 082 3 6 7 0 1 4 510
15 5 31 1
В первом наборе входных данных циклическим сдвигом, дающим максимальную стоимость, является $$$[2,1,0,5,4,3]$$$ со стоимостью $$$0+0+3+3+3+6=15$$$.
Во втором наборе входных данных циклическим сдвигом, дающим максимальную стоимость, является $$$[0,2,1]$$$ со стоимостью $$$1+1+3=5$$$.
| Codeforces Round 915 (Div. 2) |
|---|
| Закончено |
