Максимальний добуток#155

Максимальний добуток

1 секунда
512 мегабайтів
Середня

Степан останнім часом приділяв мало уваги програмуванню і як, результат, не здав залік. Тепер йому потрібно терміново вирішити наступну задачу:

Дано масив цілих чисел A_{1}, A_{2}, \dots , A_{N}, абсолютна величина елементів якого не перевищує 2. Потрібно знайти такий непорожній підвідрізок A_{l}, A_{l+1}, \dots , A_{r} цього масиву (1 \le l \le r \le N), що добуток чисел A_{l} * A_{l+1} * \dots * A_{r} є максимально можливим.

Звісно, Степан просить у вас допомоги у вирішенні даної задачі.

Вхідні дані

В першому рядку вхідного файлу знаходиться число N (1 \le N \le 200 000) — кiлькiсть елементів масиву.

В другому рядку знаходиться цiлих чисел A_{i} (-2 \le A_{i} \le 2) - елементи масиву.

Вихідні дані

Єдиний рядок вихідного файлу має містити два числа і - знайдені границі оптимального відрізка (1 \le l \le r \le N).

Якщо iснує декiлька вiдповiдей, виведiть будь-яку з них.

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Приклад 3

Loading
Loading

Оцінювання

В даній задачі кожен тест оцінюється окремо.