Migrated from Lutece 3182 罗小黑

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

罗小黑有一列正整数 $a_1,…,a_n$ 。罗小黑喜欢最大公约数大于 $1$ 的正整数可重集，所以罗小黑希望能够选择 $(l,r)$，满足：

可以从 $a_l,…,a_r$ 中选出至少 $⌈\frac{r−l+1}{2}⌉$个数，它们的最大公约数大于 $1$ 。

如果有多个满足条件的 $(l,r)$ ，罗小黑希望找到 $r−l$ 最大的。如果仍然有多个，罗小黑希望找到 $l$ 最小的。如果找不到满足条件的，则 $l=r=0$

Input

第一行包含一个整数 $n$ 。

接下来一行包含 $n$ 个整数 $a_1,…,a_n$ 。

Output

输出一行包含两个整数 $l,r$ 。

Samples

1
1

0 0

5
1 2 1 2 1

1 4

Constraints

$1\le n\le5×10^5$

$1\le a_i\le10^6$