← 返回题目列表

Codeforces · 1822/B

B. 卡琳娜和阵列

中文机器翻译题面 查看原题

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 元素。

在示例的第二个和第三个测试用例中,无需删除任何元素即可实现最大的美感。

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