Problem G
Portal Orientation

GlaDOS is busy setting the parameters on the new batch of portal devices at Aperture Science Labs.¹ However, tuning a device that allows quantum travel is no easy task! For each device, GlaDOS is given a series of dimensions in a continuous array. She must find the range of the largest series of dimensions that share at least one common prime factor. Can you help her?

Input

The first line will consist of a single integer $N$ $(1 \leq N \leq 10\, 000)$ giving the number of dimensions to analyze. This will be followed by $N$ dimensions $D_1, \ldots , D_ N$ $(0 \leq D_ i \leq 10^6)$.

Output

Output two space-separated integers, giving the starting and ending indices (inclusive) of the largest subarray (contiguous window) of dimensions sharing at least one common prime factor (recall that $1$ is not considered prime). If there are multiple valid windows of the same size, output the first window (the window with the lowest starting index among all windows of this maximum length). If there is no valid window, output $-1$. If the largest valid window has a size of $1$, output any single valid index. Arrays should be $0$-indexed.

5
2 6 3 9 7

1 3

5
1 2 3 4 5

1

10
236 118 59 1 46 128 9 17 97 34

0 2