Задача №112093. Маленькая сказка о фиолетовом бобре
Вера очень любит сочинять сказки. С детства она обладала очень богатой фантазией, ее работы были высоко оценены на многочисленных творческих конкурсах, а ее вырази- тельная речь способна невероятно точно передавать эмоции и чувства. Однако, Вера не смогла придумать красивую историю для следующей задачи по программированию:
Дан массив из целых чисел \(a_1\), \(a_2\), . . . , \(a_N\), каждый элемент которого по абсолютной величине не превосходит 2. Найдите такой непустой подотрезок \(a_l\), \(a_l\)+1, . . . , \(a_r\) этого массива (1 ≤ \(l\) ≤ \(r\) ≤ \(N\)), что произведение чисел \(a_l * a_{l+1} * ... * a_r\) является максимально возможным.
Вы, разумеется, можете посостязаться с Верой в креативности, однако мы рекомендуем вам заняться решением задачи.
В первой строке входных данных содержится число \(N (1 \le N \le 200 000)\) — число элементов массива. В следующей строке содержатся \(N\) целых чисел \(a_i\) — элементы массива \((|a_i| \le 2\)).
В единственной строке выходных данных выведите два числа \(l\) и \(r\) — искомые границы оптимального отрезка (1 ≤ \(l\) ≤ \(r\) ≤ \(N\)). В случае, если ответов несколько, выведите любой из них.
Тесты к этой задаче состоят из четырех групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп
0. Тесты 1–3. Тесты из условия, оцениваются в ноль баллов.
1. Тесты 4–15. В тестах этой группы \(N \le 60\). Эта группа оценивается в 30 баллов
2. Тесты 15–31. В тестах этой группы \(N \le 2000\). Эта группа оценивается в 30 баллов.
3. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов.
5 1 -1 2 2 1
3 5
3 -1 0 -2
2 2
7 -1 -2 -1 -2 1 2 -2
2 7