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