CF1656F.Parametric MST

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 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.