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

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

1 second
512 megabytes
Medium

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

Дано масив цілих чисел 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} є максимально можливим.

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

Input

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

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

Output

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

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

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Scoring

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