B. Максимальное произведение
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив целых чисел $$$a_1,a_2,\ldots,a_n$$$. Найдите максимум $$$a_ia_ja_ka_la_t$$$ по всем пятеркам индексов $$$(i, j, k, l, t)$$$ ($$$i<j<k<l<t$$$).

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится единственное целое число $$$t$$$ ($$$1\le t\le 2 \cdot 10^4$$$) — количество наборов входных данных. Описание наборов входных данных следует.

В первой строке описания каждого набора входных данных находится единственное целое число $$$n$$$ ($$$5\le n\le 10^5$$$) — размер массива.

Во второй строке описания каждого набора входных данных находится $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$-3\times 10^3\le a_i\le 3\times 10^3$$$) — данный массив.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите единственное целое число — ответ на задачу.

Пример
Входные данные
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
Примечание

В первом наборе входных данных выбор $$$a_1,a_2,a_3,a_4,a_5$$$ является наилучшим: $$$(-1)\cdot (-2) \cdot (-3)\cdot (-4)\cdot (-5)=-120$$$.

Во втором наборе входных данных выбор $$$a_1,a_2,a_3,a_5,a_6$$$ является наилучшим: $$$(-1)\cdot (-2) \cdot (-3)\cdot 2\cdot (-1)=12$$$.

В третьем наборе входных данных выбор $$$a_1,a_2,a_3,a_4,a_5$$$ является наилучшим: $$$(-1)\cdot 0\cdot 0\cdot 0\cdot (-1)=0$$$.

В четвертом наборе входных данных выбор $$$a_1,a_2,a_3,a_4,a_6$$$ является наилучшим: $$$(-9)\cdot (-7) \cdot (-5)\cdot (-3)\cdot 1=945$$$.