Маленькая сказка о фиолетовом бобре
시간 제한3초메모리 제한1024 MB
각 원소가 -2, -1, 0, 1, 2 중 하나인 배열에서 곱이 최대가 되는 비어 있지 않은 부분 배열을 찾습니다.
문제
Вера очень любит сочинять сказки. С детства она обладала очень богатой фантазией, ее работы были высоко оценены на многочисленных творческих конкурсах, а ее выразительная речь способна невероятно точно передавать эмоции и чувства. Однако, Вера не смогла придумать красивую историю для следующей задачи по программированию:
Дан массив из целых чисел 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). В случае, если ответов несколько, выведите любой из них.