Maximum Product Codeforces Problems solution

 Maximum Product Codeforces Problems solution 

Problems statement-

You are given an array of integers a1,a2,…,an$a_1,a_2,\dots ,a_n$. Find the maximum possible value of aiajakalat$a_i{a}_j{a}_k{a}_l{a}_t$ among all five indices (i,j,k,l,t)$(i,j,k,l,t)$ (i<j<k<l<t$i<j<k<l<t$).

Input

The input consists of multiple test cases. The first line contains an integer t$t$ (1≤t≤2⋅104$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$n$ (5≤n≤105$5\le n\le {10}^5$) — the size of the array.

The second line of each test case contains n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$ (−3×103≤ai≤3×103$-3\times {10}^3\le a_i\le 3\times {10}^3$) — given array.

It's guaranteed that the sum of n$n$ over all test cases does not exceed 2⋅105$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 a1,a2,a3,a4,a5$a_1,a_2,a_3,a_4,a_5$ is a best choice: (−1)⋅(−2)⋅(−3)⋅(−4)⋅(−5)=−120$(-1)\cdot (-2)\cdot (-3)\cdot (-4)\cdot (-5)=-120$.

In the second test case, choosing a1,a2,a3,a5,a6$a_1,a_2,a_3,a_5,a_6$ is a best choice: (−1)⋅(−2)⋅(−3)⋅2⋅(−1)=12$(-1)\cdot (-2)\cdot (-3)\cdot 2\cdot (-1)=12$.

In the third test case, choosing a1,a2,a3,a4,a5$a_1,a_2,a_3,a_4,a_5$ is a best choice: (−1)⋅0⋅0⋅0⋅(−1)=0$(-1)\cdot 0\cdot 0\cdot 0\cdot (-1)=0$.

In the fourth test case, choosing a1,a2,a3,a4,a6$a_1,a_2,a_3,a_4,a_6$ is a best choice: (−9)⋅(−7)⋅(−5)⋅(−3)⋅1=945$(-9)\cdot (-7)\cdot (-5)\cdot (-3)\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 -