F. Параметрическое MST
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$. Для любого вещественного числа $$$t$$$ рассмотрим полный взвешенный граф на $$$n$$$ вершинах $$$K_n(t)$$$ с весом ребра между вершинами $$$i$$$ и $$$j$$$, равным $$$w_{ij}(t) = a_i \cdot a_j + t \cdot (a_i + a_j)$$$.

Пусть $$$f(t)$$$ будет стоимостью минимального остовного дерева для $$$K_n(t)$$$. Определите, ограничена ли $$$f(t)$$$ сверху, и если да, то выведите максимальное значение, которое она достигает.

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

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

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

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

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

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

Для каждого набора входных данных выведите одну строку с максимальным значением $$$f(t)$$$ (можно показать, что это целое число) или «INF», если $$$f(t)$$$ не ограничена сверху.

Пример
Входные данные
5
2
1 0
2
-1 1
3
1 -1 -2
3
3 -1 -2
4
1 2 3 -4
Выходные данные
INF
-1
INF
-6
-18