B. Карина и массив
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Карины есть массив из $$$n$$$ чисел $$$a_1, a_2, a_3, \dots, a_n$$$. Она очень любит перемножать числа, поэтому она решила, что красота пары чисел — это их произведение. А красота массива — это максимальная красота пары соседних элементов в массиве.

Например, для $$$n = 4$$$, $$$a=[3, 5, 7, 4]$$$ красота массива равняется $$$\max$$$($$$3 \cdot 5$$$, $$$5 \cdot 7$$$, $$$7 \cdot 4$$$) = $$$\max$$$($$$15$$$, $$$35$$$, $$$28$$$) = $$$35$$$.

Карина очень хочет, чтобы ее массив был максимально красивым. Для того чтобы достигнуть своей цели, она может удалить из массива некоторые элементы (или не удалять ничего). После удаления в массиве должно остаться хотя бы два элемента.

К сожалению, Карина не успевает сделать все свои дела, поэтому она просит вас посчитать максимальную красоту массива, которую она может получить, удалив произвольное число элементов (возможно, ни одного).

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

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

Далее следуют описания наборов.

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

Во второй строке набора содержится $$$n$$$ целых чисел $$$a_1, a_2, a_3, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — элементы массива $$$a$$$.

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

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

Выведите $$$t$$$ чисел, каждое из которых является ответом на соответствующий набор — максимальной красотой массива, которую сможет получить Карина.

Пример
Входные данные
7
4
5 0 2 1
3
-1 1 0
5
2 0 -1 -4 0
6
-8 4 3 7 1 -9
6
0 3 -2 5 -4 -4
2
1000000000 910000000
7
-1 -7 -2 -5 -4 -6 -3
Выходные данные
10
0
4
72
16
910000000000000000
42
Примечание

В первом наборе входных данных примера для получения максимальной красоты нужно удалить $$$2$$$-й элемент.

Во втором и третьем наборах входных данных примера не нужно делать удалений для достижения максимальной красоты.

В четвертом наборе входных данных примера необходимо оставить только первый и последний элементы.