CF1822B.Karina and Array

Karina has an array of $n$ integers $a_1, a_2, a_3, \dots, a_n$. She loves multiplying numbers, so she decided that the beauty of a pair of numbers is their product. And the beauty of an array is the maximum beauty of a pair of adjacent elements in the array.

For example, for $n = 4$, $a=[3, 5, 7, 4]$, the beauty of the array is $\max$($3 \cdot 5$, $5 \cdot 7$, $7 \cdot 4$) = $\max$($15$, $35$, $28$) = $35$.

Karina wants her array to be as beautiful as possible. In order to achieve her goal, she can remove some elements (possibly zero) from the array. After Karina removes all elements she wants to, the array must contain at least two elements.

Unfortunately, Karina doesn't have enough time to do all her tasks, so she asks you to calculate the maximum beauty of the array that she can get by removing any number of elements (possibly zero).

卡琳娜有一个包含 $n$ 个整数的数组 $a_1, a_2, a_3, \dots, a_n$。她非常喜欢乘法运算，因此她定义一对数的“美感”为其乘积；而一个数组的“美感”则定义为该数组中所有相邻元素对的最大美感。

例如，当 $n = 4$、$a=[3, 5, 7, 4]$ 时，数组的美感为 $\max$($3 \cdot 5$, $5 \cdot 7$, $7 \cdot 4$) = $\max$($15$, $35$, $28$) = $35$。

卡琳娜希望她的数组尽可能美观。为了实现这一目标，她可以删除数组中的若干元素（也可以不删）。在删除完所有她想删去的元素后，数组中必须至少保留两个元素。

不幸的是，卡琳娜没有足够的时间完成所有任务，因此她请你计算：通过任意删除（包括不删除）若干元素后，所能得到的数组的最大可能美感。

The first line of the input contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The description of the test cases follows.

The first line of a test case contains an integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the length of the array $a$.

The second line of a test case contains $n$ integers $a_1, a_2, a_3, \dots, a_n$ ($-10^9 \le a_i \le 10^9$) — the elements of the array $a$.

The sum of all values of $n$ across all test cases does not exceed $2 \cdot 10^5$.

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。

接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）—— 表示数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, a_3, \dots, a_n$（$-10^9 \le a_i \le 10^9$）—— 表示数组 $a$ 的元素。

所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

Output $t$ integers, each of which is the answer to the corresponding test case — the maximum beauty of the array that Karina can get.

输出 $t$ 个整数，每个整数对应一个测试用例的答案——即卡拉娜所能得到的数组的最大美观度。

In the first test case of the example, to get the maximum beauty, you need to remove the $2$-nd element.

In the second and third test cases of the example, there is no need to remove any elements to achieve maximum beauty.

In the fourth test case of the example, you need to leave only the first and last elements.

在示例的第一个测试用例中，为获得最大美观度，你需要删除第 $2$ 个元素。

在示例的第二和第三个测试用例中，无需删除任何元素即可达到最大美观度。

在示例的第四个测试用例中，你只需保留第一个和最后一个元素。