Дан массив \(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]\).
Ваша задача — максимизировать сумму массива после применения данной операции. Найдите оптимальный отрезок для применения этой операции.
Выходные данные
Для каждого набора входных данных выведите \(2\) числа \(l\) и \(r\) (\(1 \le l \le r \le n\)) — границы заменяемого на произведение отрезка.
Если существует несколько решений, выведите любое из них.
Примечание
В первом наборе входных данных, после применения операции с параметрами \(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\), а при применении любой другой операции сумма массива уменьшится.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|