시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB52240.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). В случае, если ответов несколько, выведите любой из них.

예제 입력 1

5
1 -1 2 2 1

예제 출력 1

3 5

예제 입력 2

3
-1 0 -2

예제 출력 2

2 2

예제 입력 3

7
-1 -2 -1 -2 1 2 -2

예제 출력 3

2 7