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

Даны $$$n$$$ палочек, $$$i$$$-я палочка имеет длину $$$a_i$$$. Вы хотите выбрать непустое подмножество этих палочек и использовать их в качестве сторон многоугольника. Каждая выбранная палочка должна использоваться целиком в качестве одной стороны многоугольника. Не разрешается соединять две или более палочек концами в параллельном положении, чтобы образовать более длинную сторону.

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

  • Симметричный: существует ось симметрии такая, что когда многоугольник складывается вдоль этой оси, две половины точно совпадают.
  • Строго выпуклый: все его внутренние углы строго меньше $$$180^\circ$$$.
  • Невырожденный: никакие две последовательные стороны не накладываются друг на друга, ни одна сторона не имеет нулевую длину, и ни один угол не равен $$$180^\circ$$$.

Среди всех таких многоугольников, которые вы можете сформировать из палочек, найдите максимальный возможный периметр$$$^{\text{∗}}$$$. Если подходящий многоугольник не существует, выведите $$$0$$$.

$$$^{\text{∗}}$$$Периметр многоугольника равен сумме длин его сторон.

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

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

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

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

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

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

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

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

В первом наборе входных данных вы можете сформировать равнобедренный треугольник, используя все три палочки. Он симметричен относительно вертикальной пунктирной линии (см. левую картинку). Периметр равен сумме длин его сторон: $$$5 + 5 + 7 = 17$$$.

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

В третьем наборе входных данных невозможно сформировать невырожденный многоугольник. Если использовать все три стороны, то две стороны длины $$$5$$$ совпадут со стороной длины $$$10$$$, образуя только прямую линию с нулевой площадью.

В четвертом наборе входных данных мы можем сформировать симметричный выпуклый многоугольник, используя три палочки длиной $$$3$$$, две палочки длиной $$$5$$$ и одну палочку длиной $$$4$$$ (см. левую картинку). Последнюю палочку длиной $$$1$$$ нельзя включить, так как получившийся многоугольник больше не будет симметричным (см. правую картинку).

В пятом наборе входных данных не разрешается соединять палочки длиной $$$2$$$ и $$$3$$$, чтобы образовать палочку длиной $$$5$$$ (что дало бы первый набор входных данных). Можно доказать, что никакой симметричный невырожденный выпуклый многоугольник не может быть сформирован из любого непустого подмножества палочек.