Cho một mảng ~A~ gồm ~n~ phần tử, đánh số từ ~1...n~. Một mảng con ~(l, r)~ ~(l \le r)~ của mảng ~A~ được gọi là mảng ~GCD~ nếu ~GCD(A_l, A_{l+1}, A_{l+2}, ..., A_r) = 1~.

Tìm mảng con ~(l, r)~ của ~A~ sao cho mảng con ~(l, r)~ là một mảng ~GCD~ và có độ dài ngắn nhất.

Lưu ý: ~GCD(x_1, x_2, ..x_k)~ là ước số chung lớn nhất của các số ~x_1, x_2, ...x_k~. Ước số chung lớn nhất của các số ~x_1, x_2, ...x_k~ là một số nguyên dương ~X~ lớn nhất sao cho ~x_1, x_2, ...x_k~ đều chia hết cho ~X~.

Input

• Dòng đầu tiên chứa một số nguyên dương ~n~ là số phần tử của mảng ~A~ ~(2 \le n \le 10^5)~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa một số nguyên dương ~A_i~ ~(2 \le A_i \le 10^5)~.

Output

• Đầu ra gồm một dòng chứa ba số nguyên ~N, l, r~ lần lượt là độ dài ngắn nhất của mảng con của ~A~ là mảng ~GCD~, vị trí bắt đầu và kết thúc của mảng con đó. Nếu có nhiều mảng con ~GCD~ có độ dài ngắn nhất, tìm mảng con có vị trí bắt đầu là nhỏ nhất. Nếu không tìm được mảng con nào của ~A~ là mảng ~GCD~, xuất ra ~-1~.

Samples

Sample Input 1

5
2
6
12
3
6

Sample Output 1

4 1 4

Sample Input 2

5
2
4
6
8
14

Sample Output 2

-1

Scoring

• Subtask ~1~ (~50\%~ số test): ~2 \le n \le 1000~
• Subtask ~2~ (~50\%~ số test): Không có ràng buộc gì thêm