CF1406B Maximum Product

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

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.

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 $ .