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

Вам даны $$$n$$$ целых неотрицательных чисел $$$a_1,a_2,\ldots,a_n$$$, расположенных по кругу. Для каждого $$$1\le i \lt n$$$, $$$a_i$$$ и $$$a_{i+1}$$$ являются соседними; $$$a_1$$$ и $$$a_n$$$ также являются соседними.

Вам необходимо выполнить следующую операцию ровно $$$n-1$$$ раз:

  • Выберите любую пару соседних элементов в круге (пусть их значения будут $$$x$$$ и $$$y$$$) и объедините их в один элемент со значением $$$\max(x,y)$$$, затратив на эту операцию $$$\max(x,y)$$$.

Обратите внимание, что эта операция уменьшит размер круга на $$$1$$$ и изменит, какие пары являются соседними.

Пожалуйста, вычислите минимальные общие затраты на слияние круга в один элемент.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$).

Следующая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$0\le a_i \le 10^9$$$).

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.

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

Для каждого набора входных данных выведите одно целое число — минимальные общие затраты.

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

В первом наборе входных данных мы можем достичь затрат в $$$6$$$ на $$$[1,1,3,2]$$$ следующим образом:

  • Объедините индексы $$$1$$$ и $$$2$$$, затратив $$$1$$$. Круг становится $$$[1,3,2]$$$.
  • Объедините индексы $$$1$$$ и $$$3$$$, затратив $$$2$$$. Круг становится $$$[3,2]$$$.
  • Объедините индексы $$$1$$$ и $$$2$$$, затратив $$$3$$$. Круг становится $$$[3]$$$.

Общие затраты составляют $$$1+2+3=6$$$. Можно доказать, что невозможно достичь меньших затрат; следовательно, ответ действительно равен $$$6$$$.

Во втором наборе входных данных единственной возможной операцией является объединение двух элементов с затратами $$$2$$$.