## Maximum Product Codeforces Problems solution

Problems statement-

You are given an array of integers ${a}_{1},{a}_{2},\dots ,{a}_{n}$. Find the maximum possible value of ${a}_{i}{a}_{j}{a}_{k}{a}_{l}{a}_{t}$ among all five indices $\left(i,j,k,l,t\right)$ ($i).

Input

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},\dots ,{a}_{n}$ ($-3×{10}^{3}\le {a}_{i}\le 3×{10}^{3}$) — given array.

It's guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot {10}^{5}$.

Output

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

Example
input
Copy
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

output
Copy
-120
12
0
945

Note

In the first test case, choosing ${a}_{1},{a}_{2},{a}_{3},{a}_{4},{a}_{5}$ is a best choice: $\left(-1\right)\cdot \left(-2\right)\cdot \left(-3\right)\cdot \left(-4\right)\cdot \left(-5\right)=-120$.

In the second test case, choosing ${a}_{1},{a}_{2},{a}_{3},{a}_{5},{a}_{6}$ is a best choice: $\left(-1\right)\cdot \left(-2\right)\cdot \left(-3\right)\cdot 2\cdot \left(-1\right)=12$.

In the third test case, choosing ${a}_{1},{a}_{2},{a}_{3},{a}_{4},{a}_{5}$ is a best choice: $\left(-1\right)\cdot 0\cdot 0\cdot 0\cdot \left(-1\right)=0$.

In the fourth test case, choosing ${a}_{1},{a}_{2},{a}_{3},{a}_{4},{a}_{6}$ is a best choice: $\left(-9\right)\cdot \left(-7\right)\cdot \left(-5\right)\cdot \left(-3\right)\cdot 1=945$.

Solution -
There are 3 possible cases to maximise ans
1- all are positive(choose max possible number)
2- 4 negative 1 positive (4 minimum of all and 1 greatest positive number)
3 -2 negative and 3 positive ( Chooose 2 minimum negative and 3 highest positive number)

CODE -