Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Pair of Numbers

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputSimon has an array *a*_{1}, *a*_{2}, ..., *a*_{n}, consisting of *n* positive integers. Today Simon asked you to find a pair of integers *l*, *r* (1 ≤ *l* ≤ *r* ≤ *n*), such that the following conditions hold:

- there is integer
*j*(*l*≤*j*≤*r*), such that all integers*a*_{l},*a*_{l + 1}, ...,*a*_{r}are divisible by*a*_{j}; - value
*r*-*l*takes the maximum value among all pairs for which condition 1 is true;

Help Simon, find the required pair of numbers (*l*, *r*). If there are multiple required pairs find all of them.

Input

The first line contains integer *n* (1 ≤ *n* ≤ 3·10^{5}).

The second line contains *n* space-separated integers *a*_{1}, *a*_{2}, ..., *a*_{n} (1 ≤ *a*_{i} ≤ 10^{6}).

Output

Print two integers in the first line — the number of required pairs and the maximum value of *r* - *l*. On the following line print all *l* values from optimal pairs in increasing order.

Examples

Input

5

4 6 9 3 6

Output

1 3

2

Input

5

1 3 5 7 9

Output

1 4

1

Input

5

2 3 5 7 11

Output

5 0

1 2 3 4 5

Note

In the first sample the pair of numbers is right, as numbers 6, 9, 3 are divisible by 3.

In the second sample all numbers are divisible by number 1.

In the third sample all numbers are prime, so conditions 1 and 2 are true only for pairs of numbers (1, 1), (2, 2), (3, 3), (4, 4), (5, 5).

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/07/2021 09:25:56 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|