Maximum Product

题意翻译

一共 $t$ 组数据。 给定 $n$ 个数、让你找 $5$ 个数，让它们的乘积最大。 每个数可正可负。

题目描述

You are given an array of integers $ a_1,a_2,\ldots,a_n $ . Find the maximum possible value of $ a_ia_ja_ka_la_t $ among all five indices $ (i, j, k, l, t) $ ( $ i<j<k<l<t $ ).

输入输出格式

输入格式

The input consists of multiple test cases. The first line contains an integer $ t $ ( $ 1\le t\le 2 \cdot 10^4 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 5\le n\le 10^5 $ ) — the size of the array. The second line of each test case contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ -3\times 10^3\le a_i\le 3\times 10^3 $ ) — given array. It's guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot 10^5 $ .

输出格式

For each test case, print one integer — the answer to the problem.

输入输出样例

输入样例 #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

说明

In the first test case, choosing $ a_1,a_2,a_3,a_4,a_5 $ is a best choice: $ (-1)\cdot (-2) \cdot (-3)\cdot (-4)\cdot (-5)=-120 $ . In the second test case, choosing $ a_1,a_2,a_3,a_5,a_6 $ is a best choice: $ (-1)\cdot (-2) \cdot (-3)\cdot 2\cdot (-1)=12 $ . In the third test case, choosing $ a_1,a_2,a_3,a_4,a_5 $ is a best choice: $ (-1)\cdot 0\cdot 0\cdot 0\cdot (-1)=0 $ . In the fourth test case, choosing $ a_1,a_2,a_3,a_4,a_6 $ is a best choice: $ (-9)\cdot (-7) \cdot (-5)\cdot (-3)\cdot 1=945 $ .