G. Игра с треугольниками: Сезон 2
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Фронтмен приветствует вас в этом финальном раунде игры на выживание.

Есть правильный многоугольник с $$$n$$$ сторонами ($$$n \ge 3$$$). Вершины индексируются как $$$1,2,\ldots,n$$$ по часовой стрелке. На каждой вершине $$$i$$$ розовые солдаты написали положительное целое число $$$a_i$$$. С этим правильным многоугольником вы будете играть в игру, определяемую следующим образом.

Изначально ваш счет равен $$$0$$$. Затем вы выполняете следующую операцию любое количество раз, чтобы увеличить свой счет.

  • Выберите $$$3$$$ разные вершины $$$i$$$, $$$j$$$, $$$k$$$, которые вы не выбирали ранее, и проведите треугольник, образованный этими тремя вершинами.
    • Затем ваш счет увеличивается на $$$a_i \cdot a_j \cdot a_k$$$.
    • Однако вы не можете выполнить эту операцию, если треугольник имеет положительную общую площадь с любыми из ранее нарисованных треугольников.
Пример состояния после двух операций показан слева. Состояние справа невозможно, так как два треугольника имеют положительную общую площадь.

Ваша цель — максимизировать счет. Пожалуйста, найдите максимальный счет, который вы можете получить в этой игре.

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

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

Первая строка каждого набора содержит одно целое число $$$n$$$ — количество вершин ($$$3 \le n \le 400$$$).

Вторая строка каждого набора содержит $$$a_1,a_2,\ldots,a_n$$$ — целые числа, написанные на вершинах ($$$1 \le a_i \le 1000$$$).

Гарантируется, что сумма $$$n^3$$$ по всем наборам входных данных не превышает $$$400^3$$$.

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

Для каждого набора входных данных выведите максимальный счет, который вы можете получить, на отдельной строке.

Пример
Входные данные
6
3
1 2 3
4
2 1 3 4
6
2 1 2 1 1 1
6
1 2 1 3 1 5
9
9 9 8 2 4 4 3 5 3
9
9 9 3 2 4 4 8 5 3
Выходные данные
6
24
5
30
732
696
Примечание

В первом примере вы можете нарисовать только один треугольник. Максимальный счет $$$6$$$ достигается, рисуя треугольник с $$$i=1$$$, $$$j=2$$$, $$$k=3$$$.

Во втором примере вы можете нарисовать только один треугольник. Максимальный счет $$$24$$$ достигается, рисуя треугольник с $$$i=1$$$, $$$j=3$$$, $$$k=4$$$.

В третьем примере вы можете нарисовать два треугольника. Существует последовательность из двух операций, которая приводит к счету $$$5$$$, что является максимальным.

В четвертом примере вы можете нарисовать два треугольника. Однако рисование двух треугольников приводит к счету либо $$$6+5=11$$$, $$$15+2=17$$$, либо $$$10+3=13$$$. Максимальный счет $$$30$$$ достигается, рисуя только один треугольник с $$$i=2$$$, $$$j=4$$$, $$$k=6$$$.

В пятом примере вы можете нарисовать три треугольника. Максимальный счет $$$732$$$ достигается, рисуя три треугольника следующим образом.