Simon has an array a1, a2, ..., an, 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:

  1. there is integer j (l ≤ j ≤ r), such that all integers al, al + 1, ..., ar are divisible by aj; 
  2. 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·105).

The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 106).

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).
import java.io.*;
import java.math.*;
import java.util.*;
public class Main
{
    static long mod=((long)1e9)+7;//toString
    public static int gcd(int a,int b){if(b==0)return a;else return gcd(b,a%b);}
    public static long pow_mod(long x,long y){long res=1;x=x%mod;while(y > 0){if((y & 1)==1)res=(res * x)%mod;y=y>>1;x =(x * x)%mod;}return res;}
    public static int lower_bound(int[]arr,int val){int lo=0;int hi=arr.length-1;while(lo<hi){int mid=lo+((hi-lo+1)/2);if(arr[mid]==val){return mid;}else if(arr[mid]>val){hi=mid-1;}else lo=mid;}if(arr[lo]<=val)return lo;else return -1;}
    public static int upper_bound(int[]arr,int val){int lo=0;int hi=arr.length-1;while(lo<hi){int mid=lo+((hi-lo)/2);if(arr[mid]==val){return mid;}else if(arr[mid]>val){hi=mid;;}else lo=mid+1;}if(arr[lo]>=val)return lo;else return -1;}
    static int[][] gcd_table;static int[][] min_table;static int[] log;
    static int[] arr;
    public static int gcd_query(int l , int r){
        int ans = 0;
        for(int i = 20; i >= 0; --i){
            if((1 << i) <= (r - l + 1)){
                ans = gcd(ans , gcd_table[l][i]);
                l += (1 << i);
            }
        }
        return ans;
    }
    public static int min_query(int l , int r){
        int j = log[r - l + 1];
        return Math.min(min_table[l][j] , min_table[r - (1 << (j)) + 1][j]);
    }
    public static boolean isPossible(int k){
        for(int i = 0; (i + k) < arr.length; ++i){
            if(min_query(i , (i + k)) == gcd_query(i , (i + k))){
                return true;
            }
        }
        return false;
    }
    public static void main (String[] args) throws java.lang.Exception
    {
        Reader sn = new Reader();
        Print p = new Print();
        int n = sn.nextInt();
        arr = new int[n];
        for(int i = 0; i < n; ++i){
            arr[i] = sn.nextInt();
        }
        gcd_table = new int[n][21];
        min_table = new int[n][21];
        log = new int[n + 1];
        for(int i = 0; i < n; ++i){
            gcd_table[i][0] = arr[i];
        }
        for(int i = 1; i <= 20; ++i){
            for(int j = 0; (j + (1 << i)) <= n; ++j){
                gcd_table[j][i] = gcd(gcd_table[j][i - 1] , 
                                    gcd_table[j + (1 << (i - 1))][i - 1]);
            }
        }
        for(int i = 0; i < n; ++i){
            min_table[i][0] = arr[i];
        }
        for(int j = 1; j <= 20; ++j){
            for(int i = 0; (i + (1 << j)) <= n; ++i){
                min_table[i][j] = Math.min(min_table[i][j - 1],
                                min_table[i + (1 << (j - 1))][j - 1]);
            }
        }
        log[1] = 0;
        for(int i = 2; i <= n; ++i){
            log[i] = log[i / 2] + 1;
        }
        int lo = 0;
        int hi = n - 1;
        while(lo < hi){
            int mid = lo + ((hi - lo + 1) >> 1);
            if(isPossible(mid)){
                lo = mid;
            }
            else{
                hi = mid - 1;
            }
        }
        int c = 0;
        ArrayList<Integer> ans = new ArrayList<Integer>();
        for(int i = 0; (i + lo)< n; ++i){
            if(min_query(i , i + lo) == gcd_query(i , i + lo)){
                c++;
                ans.add(i);
            }
        }
        p.print(Integer.toString(c)+" "+Integer.toString(lo));
        p.printLine(" ");
        for(int i = 0; i < ans.size(); ++i){
            p.print(Integer.toString(ans.get(i) + 1)+" ");
        }
        p.close();
    }
}
class Pair implements Comparable<Pair> {
		int val;
		int in;
		Pair(int a, int b){
			val=a;
	        in=b;
		}
		@Override
		public int compareTo(Pair o) {
			if(val==o.val)
			return Integer.compare(in,o.in);
			else
			return Integer.compare(val,o.val);
		}}
class Reader
    {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;
        public boolean isSpaceChar(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; }
        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1)
            {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }
        
        public String readWord()throws IOException
        {
		int c = read();
		while (isSpaceChar(c)) c = read();        
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		}while (!isSpaceChar(c));
		return res.toString();
	    } 
	
        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do
            {
                ret = ret * 10 + c - '0';
            }  while ((c = read()) >= '0' && c <= '9');
 
            if (neg)
                return -ret;
            return ret;
        }
 
        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }
 
        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
 
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
 
            if (c == '.')
            {
                while ((c = read()) >= '0' && c <= '9')
                {
                    ret += (c - '0') / (div *= 10);
                }
            }
 
            if (neg)
                return -ret;
            return ret;
        }
 
        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }
 
        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }
 
        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }
class Print
{
    private final BufferedWriter bw;
    public Print()
    {
        bw=new BufferedWriter(new OutputStreamWriter(System.out));
    }
    public void print(String str)throws IOException
    {
        bw.append(str);
    }
    public void printLine(String str)throws IOException
    {
        print(str);
        bw.append("\n");
    }
    public void close()throws IOException
    {
        bw.close();
    }}