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).
/**
 * Created by Aminul on 11/16/2017.
 */

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

public class CF359D {
    static RmqSparseTable st;
    static int n, a[];
    public static void main(String[] args) throws Exception {
        FastReader in = new FastReader(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        n = in.nextInt();
        a = new int[n+1];

        for(int i = 1; i <= n; i++){
            a[i] = in.nextInt();
        }
        st = new RmqSparseTable(a);

        int max = 0;
        List<Integer> list[] = new List[(int)5e5+50];
        list[0] = new ArrayList<>();

        for(int i = 1; i <= n; i++){
            int l = bSearch_1(i), r = bSearch_2(i);
            //debug(i, l, r);
            max = Math.max(max, r-l);
            if(list[r-l] == null) list[r-l] = new ArrayList<>();
            list[r-l].add(l);
        }



        TreeSet<Integer> ans = new TreeSet<>(list[max]);
        pw.println(ans.size()+" "+max);
        for(int i : ans){
            pw.print(i+" ");
        }

        pw.println();

        pw.close();
    }

    static int bSearch_1(int x){
        int lo  = 1, hi = x, mid = (lo+hi)/2;
        int temp = 0;
        while(lo < hi){
            mid = (lo+hi)/2;
            temp = st.query(mid, x);
            if( temp % a[x] == 0) hi = mid;
            else lo = mid+1;
        }
        if(st.query(lo, x) % a[x] != 0) return lo+1;
        return lo;
    }

    static int bSearch_2(int x){
        int lo  = x, hi = n, mid = (lo+hi)/2;
        int temp = 0;
        while(lo < hi){
            mid = (lo+hi)/2;
            temp = st.query(x, mid);
            if( temp % a[x] != 0) hi = mid;
            else lo = mid+1;
        }
        if(lo > n || st.query(x, lo) % a[x] != 0) return lo-1;
        return lo;
    }


    static int gcd(int p, int q) {
        if (q == 0) return p;
        else return gcd(q, p % q);
    }

    static class RmqSparseTable {

        int[] logTable;
        int[][] rmq;
        int[] a;

        public RmqSparseTable(int[] a) {
            this.a = a;
            int n = a.length;

            logTable = new int[n + 1];
            for (int i = 2; i <= n; i++)
                logTable[i] = logTable[i >> 1] + 1;

            rmq = new int[logTable[n] + 1][n];

            for (int i = 0; i < n; ++i)
                rmq[0][i] = a[i];

            for (int k = 1; (1 << k) < n; ++k) {
                for (int i = 0; i + (1 << k) <= n; i++) {
                    int x = rmq[k - 1][i];
                    int y = rmq[k - 1][i + (1 << k - 1)];
                    rmq[k][i] = gcd(x, y);
                }
            }
        }

        public int query(int i, int j) {
            int k = logTable[j - i];
            int x = rmq[k][i];
            int y = rmq[k][j - (1 << k) + 1];
            return gcd(x, y);
        }
    }


    static class SegTree{
        int n, seg[] = new int[(int)1e6];
        SegTree(int N){
            n = N;
        }
        void build(int p, int s, int e){
            if(s == e){
                seg[p] = a[s];
                return;
            }
            if(s > e) return;
            int m = (s+e)/2, l = 2*p, r = l + 1;
            build(l, s, m);
            build(r, m+1, e);
            seg[p] = gcd(seg[l], seg[r]);
        }

        int query(int l, int r){
            return query(1, 1, n, l, r);
        }

        int query(int p, int s, int e, int a, int b){
            if(s >= a && e <= b){
                return seg[p];
            }
            if(s > e || s > b || e < a) return -1;
            int m = (s+e)/2, l = 2*p, r = l+1;
            int q1 = query(l, s, m, a, b), q2 = query(r, m+1, e, a, b);
            if(q1 == -1) return q2;
            if(q2 == -1) return q1;
            return gcd(q1, q2);
        }
    }

    static void debug(Object... obj) {
        System.err.println(Arrays.deepToString(obj));
    }

    static class FastReader {
        InputStream is;
        private byte[] inbuf = new byte[1024];
        private int lenbuf = 0, ptrbuf = 0;
        static final int ints[] = new int[128];

        public FastReader(InputStream is) {
            for (int i = '0'; i <= '9'; i++) ints[i] = i - '0';
            this.is = is;
        }

        public int readByte() {
            if (lenbuf == -1) throw new InputMismatchException();
            if (ptrbuf >= lenbuf) {
                ptrbuf = 0;
                try {
                    lenbuf = is.read(inbuf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (lenbuf <= 0) return -1;
            }
            return inbuf[ptrbuf++];
        }

        public boolean isSpaceChar(int c) {
            return !(c >= 33 && c <= 126);
        }

        public int skip() {
            int b;
            while ((b = readByte()) != -1 && isSpaceChar(b)) ;
            return b;
        }

        public String next() {
            int b = skip();
            StringBuilder sb = new StringBuilder();
            while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }

        public int nextInt() {
            int num = 0, b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
            if (b == '-') {
                minus = true;
                b = readByte();
            }

            while (true) {
                if (b >= '0' && b <= '9') {
                    num = (num << 3) + (num << 1) + ints[b];
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public long nextLong() {
            long num = 0;
            int b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
            if (b == '-') {
                minus = true;
                b = readByte();
            }

            while (true) {
                if (b >= '0' && b <= '9') {
                    num = (num << 3) + (num << 1) + ints[b];
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
       /* public char nextChar() {
            return (char)skip();
        }*/

        public char[] next(int n) {
            char[] buf = new char[n];
            int b = skip(), p = 0;
            while (p < n && !(isSpaceChar(b))) {
                buf[p++] = (char) b;
                b = readByte();
            }
            return n == p ? buf : Arrays.copyOf(buf, p);
        }

        /*private char buff[] = new char[1005];
        public char[] nextCharArray(){
            int b = skip(), p = 0;
            while(!(isSpaceChar(b))){
                buff[p++] = (char)b;
                b = readByte();
            }
            return Arrays.copyOf(buff, p);
        }*/
    }
}