| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 5 | 2 | 2 | 40.000% |
Вера очень любит сочинять сказки. С детства она обладала очень богатой фантазией, ее работы были высоко оценены на многочисленных творческих конкурсах, а ее выразительная речь способна невероятно точно передавать эмоции и чувства. Однако, Вера не смогла придумать красивую историю для следующей задачи по программированию:
Дан массив из целых чисел a1, a2, . . . , aN , каждый элемент которого по абсолютной величине не превосходит 2. Найдите такой непустой подотрезок al, al+1, . . . , ar этого массива (1 ≤ l ≤ r ≤ N), что произведение чисел al · al+1 · . . . · ar является максимально возможным.
Вы, разумеется, можете посостязаться с Верой в креативности, однако мы рекомендуем вам заняться решением задачи.
В первой строке входных данных содержится число N (1 ≤ N ≤ 200 000) — число элементов массива. В следующей строке содержатся N целых чисел ai — элементы массива (|ai| ≤ 2).
В единственной строке выходных данных выведите два числа l и r — искомые границы оптимального отрезка (1 ≤ l ≤ r ≤ N). В случае, если ответов несколько, выведите любой из них.
5 1 -1 2 2 1
3 5
3 -1 0 -2
2 2
7 -1 -2 -1 -2 1 2 -2
2 7