题目描述

咕噜有一个长度为 n 的整数数组 a₁, a₂, a₃, …, aₙ。
他认为一对数字的美感在于它们的乘积，数组的美感定义为：
数组中所有相邻元素乘积中的最大值。

例如：
当 n = 4，数组 a = [3, 5, 7, 4] 时，
美感 = max(3×5, 5×7, 7×4) = max(15, 35, 28) = 35。

为了使数组尽可能美丽，咕噜可以从中删除任意数量的元素（也可以一个都不删）。
删除后，数组必须至少包含两个元素。
请你计算：通过合理删除后，数组所能达到的最大美感值。

输入格式

第一行：一个整数 t（1 ≤ t ≤ 10⁴），表示测试数据组数。

接下来每组数据包含两行：

• 第一行：一个整数 n（2 ≤ n，所有 n 总和 ≤ 2×10⁵），表示数组长度
• 第二行：n 个整数 a₁, a₂, …, aₙ（−10⁹ ≤ aᵢ ≤ 10⁹），表示数组的元素值

输出格式

对于每组测试用例，输出一行，表示通过删除元素后所能得到的数组最大美感。

输入样例 #1

7  
4  
5 0 2 1  
3  
-1 1 0  
5  
2 0 -1 -4 0  
6  
-8 4 3 7 1 -9  
6  
0 3 -2 5 -4 -4  
2  
1000000000 910000000  
7  
-1 -7 -2 -5 -4 -6 -3  

输出样例 #1

10  
0  
4  
72  
16  
910000000000000000  
42