You are given an array of integers. Find the maximum possible product of five elements from the array, where the indices of these elements are in strictly increasing order.

Input

The input consists of multiple test cases. The first line contains an enteger t (1 ≤ t ≤ 2 × 10^4) — the number of test cases. The description of the test cases follows.

For each test case:

• The first line contains a single integer n (5 ≤ n ≤ 10^5) — the size of the array.
• The second line contains n integers a1, a2, …, an (-3 × 10^3 ≤ ai ≤ 3 × 10^3) — the given array.

It is guaranteed that the sum of n over all test cases does not exceed 2 × 10^5.

Output

For each test case, output one integer — the maximum product of five elements with increasing indices.

Sample Input and Output

Input	Output
```
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
```	```
-120
12
0
945
```

Explanation of Sample Cases

• In the first test case, selecting all five elements gives the product (-1) × (-2) × (-3) × (-4) × (-5) = -120.
• In the second test case, selecting elements at indices 1, 2, 3, 5, and 6 yields (-1) × (-2) × (-3) × 2 × (-1) = 12.
• In the third test case, selecting elements at indices 1, 2, 3, 4, and 5 results in (-1) × 0 × 0 × 0 × (-1) = 0.
• In the fourth test case, selecting elements at indices 1, 2, 3, 4, and 6 gives (-9) × (-7) × (-5) × (-3) × 1 = 945.

Problem Analysis

To find the maximum product of five elements from the array, we need to consider the effects of negative numbers and zeros. Sorting the array allows us to easily access the smallest and largest values. The maximum product can arise from several combinations:

1. The product of the five largest numbers.
2. The product of the five smallest numbers.
3. The product of the two smallest numbers and the three largest numbers.
4. The product of the four smallest numbers and the largest number.

By evaluating these four cases, we can determine the maximum possible product.

Python Implementation

def compute_max_product(values):
    # Sort the array in ascending order
    values.sort()
    
    # Case 1: Product of the five largest numbers
    product_largest = values[-1] * values[-2] * values[-3] * values[-4] * values[-5]
    
    # Case 2: Product of the five smallest numbers
    product_smallest = values[0] * values[1] * values[2] * values[3] * values[4]
    
    # Case 3: Product of the two smallest and three largest numbers
    product_mix1 = values[0] * values[1] * values[-1] * values[-2] * values[-3]
    
    # Case 4: Product of the four smallest and the largest number
    product_mix2 = values[0] * values[1] * values[2] * values[3] * values[-1]
    
    # Return the maximum among all cases
    return max(product_largest, product_smallest, product_mix1, product_mix2)

# Read input and process each test case
num_test_cases = int(input().strip())
for _ in range(num_test_cases):
    array_size = int(input().strip())
    array_elements = list(map(int, input().split()))
    print(compute_max_product(array_elements))

Execution Example

Running the above code with the sample input produces the expected output:

-120
12
0
945