Parametric MST

给定一张 $n$ 个点的无向完全图 $K_n(t)$ ，点 $i$ 和点 $j$ 之间的边的边权 $w_{i,j}(t)$ 为 $a_i*a_j+t*(a_i+a_j)$ ，其中 $t$ 为任意实数。 定义 $f(t)$ 为 $K_n(t)$ 的最小生成树的边权和。输出 $f(t)$ 的最大值，无最大值则输出 `INF` 。 $T$ 组数据。 $1\le T\le 10^4$ ， $2\le n \le 2*10^5$ ， $\sum n\le 2*10^5$ ， $-10^6\le a_i\le 10^6$ 。

You are given $ n $ integers $ a_1, a_2, \ldots, a_n $ . For any real number $ t $ , consider the complete weighted graph on $ n $ vertices $ K_n(t) $ with weight of the edge between vertices $ i $ and $ j $ equal to $ w_{ij}(t) = a_i \cdot a_j + t \cdot (a_i + a_j) $ . Let $ f(t) $ be the cost of the [minimum spanning tree](https://en.wikipedia.org/wiki/Minimum_spanning_tree) of $ K_n(t) $ . Determine whether $ f(t) $ is bounded above and, if so, output the maximum value it attains.

The input consists of multiple test cases. The first line contains a single integer $ T $ ( $ 1 \leq T \leq 10^4 $ ) — the number of test cases. Description of the test cases follows. The first line of each test case contains an integer $ n $ ( $ 2 \leq n \leq 2 \cdot 10^5 $ ) — the number of vertices of the graph. The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ -10^6 \leq a_i \leq 10^6 $ ). The sum of $ n $ for all test cases is at most $ 2 \cdot 10^5 $ .

For each test case, print a single line with the maximum value of $ f(t) $ (it can be shown that it is an integer), or INF if $ f(t) $ is not bounded above.

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