Karina 有一个 $$$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$$$。
卡琳娜希望她的阵列尽可能漂亮。为了实现她的目标,她可以从数组中删除一些元素(可能为零)。卡琳娜 (Karina) 删除她想要删除的所有元素后,数组必须至少包含两个元素。
不幸的是,卡琳娜没有足够的时间来完成她的所有任务,因此她要求您计算她通过删除任意数量的元素(可能为零)可以获得的数组的最大美感。
输入
输入的第一行包含一个整数 $$$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$$$。
输出
输出 $$$t$$$ 个整数,每个整数都是对应测试用例的答案——Karina 可以获得的数组的最大美感。
示例
输入 #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
注意
在示例的第一个测试用例中,为了获得最大的美感,需要删除 $$$2$$$-nd 元素。
在示例的第二个和第三个测试用例中,无需删除任何元素即可实现最大的美感。
在示例的第四个测试用例中,您只需保留第一个和最后一个元素。