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

Дан массив $$$a$$$, состоящий из $$$n$$$ целых чисел. Для каждого $$$i$$$ ($$$1 \le i \le n$$$) верно неравенство: $$$-2 \le a_i \le 2$$$.

Вы можете удалить любое количество (возможно, $$$0$$$) элементов из начала массива и любое количество (возможно, $$$0$$$) элементов из конца массива. При этом разрешается удалить весь массив.

Вам нужно ответить на вопрос: сколько элементов нужно удалить из начала массива и сколько элементов нужно удалить из конца массива, чтобы в результате получился массив, произведение элементов которого максимально. Если существует более одного способа получить массив с максимальным произведением элементов, разрешается вывести любой из них.

Произведение чисел на пустом массиве (массиве длины $$$0$$$) следует считать равным $$$1$$$.

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

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

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

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

В следующей строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$|a_i| \le 2$$$) — элементы массива $$$a$$$.

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

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

Для каждого набора входных данных выведите два неотрицательных целых числа $$$x$$$ и $$$y$$$ ($$$0 \le x + y \le n$$$) — такие, что произведение чисел массива после удаления $$$x$$$ элементов с начала и $$$y$$$ элементов с конца, будет максимальным.

Если есть несколько способов получения максимального произведения, разрешается вывести любой. Произведение чисел на пустом массиве считать равным $$$1$$$.

Пример
Входные данные
5
4
1 2 -1 2
3
1 1 -2
5
2 0 -2 2 -1
3
-2 -1 -1
3
-1 -2 -2
Выходные данные
0 2
3 0
2 0
0 1
1 0
Примечание

В первом наборе входных данных примера максимальное значение произведения равно $$$2$$$. Таким образом, можно либо удалить три первых элемента (получим массив $$$[2]$$$), либо два последних и один первый элементы (также получим массив $$$[2]$$$), либо два последних (получим массив $$$[1, 2]$$$). Таким образом, в первом наборе подходят ответы: «3 0», «1 2» или «0 2».

Во втором наборе максимальное значение произведения равно $$$1$$$. Тогда можно удалить все элементы из массива, так как значение произведения на пустом массиве будет равно $$$1$$$. Таким образом, подходит ответ «3 0», но есть и другие возможные ответы.

В третьем наборе можно удалить два первых элемента массива. Тогда получим массив: $$$[-2, 2, -1]$$$. Произведение элементов полученного массива равно: $$$(-2) \cdot 2 \cdot (-1) = 4$$$. Это значение является максимально возможным из тех, которые можно получить. Таким образом, для этого набора входных данных подходит ответ «2 0».