← 返回题目列表

Codeforces · 1406/B

B. 最大产品

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

给定一个整数数组 $$$a_1,a_2,\ldots,a_n$$$。在所有五个索引 $$$(i, j, k, l, t)$$$ ($$$i<j<k<l<t$$$) 中查找 $$$a_ia_ja_ka_la_t$$$ 的最大可能值。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 2 \cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$5\le n\le 10^5$$$) — 数组的大小。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$-3\times 10^3\le a_i\le 3\times 10^3$$$) — 给定数组。

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

输出

对于每个测试用例,打印一个整数 - 问题的答案。

示例

输入 #1

4
5
-1 -2 -3 -4 -5
6
-1 -2 -3 1 2 -1
6
-1 0 0 0 -1 -1
6
-9 -7 -5 -3 -2 1

输出 #1

-120
12
0
945

注意

在第一个测试用例中,选择 $$$a_1,a_2,a_3,a_4,a_5$$$ 是最佳选择:$$$(-1)\cdot (-2) \cdot (-3)\cdot (-4)\cdot (-5)=-120$$$。

在第二个测试用例中,选择 $$$a_1,a_2,a_3,a_5,a_6$$$ 是最佳选择:$$$(-1)\cdot (-2) \cdot (-3)\cdot 2\cdot (-1)=12$$$。

在第三个测试用例中,选择 $$$a_1,a_2,a_3,a_4,a_5$$$ 是最佳选择:$$$(-1)\cdot 0\cdot 0\cdot 0\cdot (-1)=0$$$。

在第四个测试用例中,选择 $$$a_1,a_2,a_3,a_4,a_6$$$ 是最佳选择:$$$(-9)\cdot (-7) \cdot (-5)\cdot (-3)\cdot 1=945$$$。