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

Предположим, вы стоите на плоскости $$$XY$$$ в точке $$$(0, 0)$$$ и хотите попасть в точку $$$(n, n)$$$.

Вы можете двигать только в двух направлениях:

  • вправо, т. е. горизонтально и в направлении увеличения $$$x$$$ коодинаты,
  • или вверх, т. е. вертикально и в направлении увеличения $$$y$$$ координаты.

Другими словами, ваш путь имеет следующую структуру:

  • первоначально, вы выбираете: пойти вправо или вверх;
  • далее вы проходите некоторое положительное целое расстояние в выбранном направлении (расстояния можно выбирать независимо);
  • далее вы меняете направление движения (от «вправо» к «вверх», либо от «вверх» к «вправо») и повторяете процесс.

Вам не нравится менять свое направление слишком много раз, а потому вы сделаете не более $$$n - 1$$$ изменений направления.

В результате ваш путь будет представлять ломаную от $$$(0, 0)$$$ к $$$(n, n)$$$, состоящую из не более чем $$$n$$$ отрезков, каждый из которых имеет положительную целую длину, а также вертикальные и горизонтальные отрезки идут по очереди.

Не все пути равны. У вас есть $$$n$$$ целых чисел $$$c_1, c_2, \dots, c_n$$$, где $$$c_i$$$ — это цена $$$i$$$-го отрезка.

Используя эти цены, можно определить цену пути как сумму длин отрезков этого пути умноженных на их стоимости, т. е. если путь состоит из $$$k$$$ отрезков ($$$k \le n$$$), то цена пути равна $$$\sum\limits_{i=1}^{k}{c_i \cdot length_i}$$$ (отрезки нумеруются от $$$1$$$ по $$$k$$$ в порядке их обхода).

Определите путь минимальной стоимости и выведите его цену.

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

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

В первой строке каждого набора задано одно целое число $$$n$$$ ($$$2 \le n \le 10^5$$$).

Во второй строке каждого набора заданы $$$n$$$ целых чисел $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le 10^9$$$) — цены каждого отрезка.

Гарантируется, что сумма $$$n$$$ не превосходит $$$10^5$$$.

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

Для каждого набора входных данных вы должны вывести минимальную цену пути из $$$(0, 0)$$$ в $$$(n, n)$$$, состоящего из не более $$$n$$$ чередующихся отрезков.

Пример
Входные данные
3
2
13 88
3
2 3 1
5
4 3 2 1 4
Выходные данные
202
13
19
Примечание

В первом примере из условия, чтобы достигнуть $$$(2, 2)$$$, нужно сделать хотя бы один поворот, и путь может состоять из $$$2$$$ отрезков: горизонтального длины $$$2$$$ и вертикального длины $$$2$$$. Стоимость равна $$$2 \cdot c_1 + 2 \cdot c_2 = 26 + 176 = 202$$$.

Во втором примере можно построить путь из $$$3$$$ отрезков: длины $$$1$$$, длины $$$3$$$ и длины $$$2$$$. Стоимость равна $$$1 \cdot 2 + 3 \cdot 3 + 2 \cdot 1 = 13$$$.

В третьем примере можно построить путь из $$$4$$$ отрезков: длины $$$1$$$, длины $$$1$$$, длины $$$4$$$ и длины $$$4$$$. Стоимость равна $$$1 \cdot 4 + 1 \cdot 3 + 4 \cdot 2 + 4 \cdot 1 = 19$$$.