UOJ Logo

NOI.AC

1S 512MB

#1529. 三只小猪的力量

统计

三只小猪的力量

三只小猪遇上了大灰狼小明,于是三只小猪躲在家中寻找可以对付大灰狼的武器。小猪家中有n把武器,美把武器有一个能力值,可能是正的也可能是负的。三只小猪心有灵犀,他们搭配后总的力量为他们三个人的能力值之积。大灰狼马上就要进来了,希望你们可以再最短的时间内找到最大的能力值之积。众所周知,一个武器只能被一个小猪占有。

输入说明

首先收入一个T,代表有T组数据。(T <= 10)

首先输入一个n,代表有n把武器。

接下来一行有n个数,每个数代表一个武器的能力值vi (abs(vi) <= $2^{31}$ )

对于 10% 的测试样例 n <= 5; 对于 30% 的测试样例 n <= 200; 对于 70% 的测试样例 n <= 100000; 对于 100% 的测试样例 3 <= n <= 2000000; (期望时间O(n), 期望空间O(1));

输出说明

输出T个数。

每组数据输出一个值。

Example

3
4
3 4 1 2
5
-1 -2 -3 -4 -5
5
-2 -2 3 3 -5

输出:

24
-6
30