G. Замените на произведение
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$ из $$$n$$$ целых положительных чисел. Вам нужно ровно один раз сделать следующую операцию:

  • Выбрать $$$2$$$ целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$) и заменить подотрезок $$$a[l \ldots r]$$$ на единственный элемент: произведение элементов этого отрезка $$$(a_l \cdot \ldots \cdot a_r)$$$.

Например, если к массиву $$$[5, 4, 3, 2, 1]$$$ применить операцию с параметрами $$$l = 2, r = 4$$$, массив превратится в $$$[5, 24, 1]$$$.

Ваша задача — максимизировать сумму массива после применения данной операции. Найдите оптимальный отрезок для применения этой операции.

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

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

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

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

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

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

Для каждого набора входных данных выведите $$$2$$$ числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$) — границы заменяемого на произведение отрезка.

Если существует несколько решений, выведите любое из них.

Пример
Входные данные
9
4
1 3 1 3
4
1 1 2 3
5
1 1 1 1 1
5
10 1 10 1 10
1
1
2
2 2
3
2 1 2
4
2 1 1 3
6
2 1 2 1 1 3
Выходные данные
2 4
3 4
1 1
1 5
1 1
1 2
2 2
4 4
1 6
Примечание

В первом наборе входных данных, после применения операции с параметрами $$$l = 2, r = 4$$$, массив из $$$[1, 3, 1, 3]$$$ превращается в $$$[1, 9]$$$, с суммой $$$10$$$. Несложно видеть, что при замене любого другого отрезка на произведение, сумма будет меньше $$$10$$$.

Во втором наборе входных данных, после применения операции с параметрами $$$l = 3, r = 4$$$, массив из $$$[1, 1, 2, 3]$$$ превращается в $$$[1, 1, 6]$$$, с суммой $$$8$$$. Несложно видеть, что при замене любого другого отрезка на произведение, сумма будет меньше $$$8$$$.

В третьем наборе входных данных, оптимально будет выбрать любую операцию с $$$l = r$$$, тогда сумма массива останется равна $$$5$$$, а при применении любой другой операции сумма массива уменьшится.