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.util.*;

public class Main {
    FastScanner in;
    PrintWriter out;

    static final String FILE = "";

    int gcd(int a, int b) {
        int c;
        while (a != 0) {
            c = a;
            a = b % a;
            b = c;
        }
        return b;
    }

    public 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);
        }
    }

    int n;
    int ms[];
    int left[], right[];
    RmqSparseTable table;


    void calcLeft(int v) {
        int a = 0, b = v;
        while (a != b) {
            int la = a, lb = b;
            int mid = (a + b) / 2;
            if(table.query(mid, v) == ms[v])
                b = mid;
            else
                a = mid;

            if(la == a && lb == b) {
                if(table.query(a, v) == ms[v])
                    b = a;
                else
                    a = b;
            }
        }
        left[v] = a;
    }

    void calcRight(int v) {
        int a = v, b = n - 1;
        while (a != b) {
            int la = a, lb = b;
            int mid = (a + b) / 2;
            if(table.query(v, mid) == ms[v])
                a = mid;
            else
                b = mid;

            if(la == a && lb == b) {
                if(table.query(v, b) == ms[v])
                    a = b;
                else
                    b = a;
            }
        }
        right[v] = a;
    }

    public void solve() {
        n = in.nextInt();
        ms = new int[n];
        left = new int[n];
        right = new int[n];

        for (int i = 0; i < n; i++)
            ms[i] = in.nextInt();
        table = new RmqSparseTable(ms);

        for (int i = 0; i < n; i++)
            calcLeft(i);
        for (int i = 0; i < n; i++)
            calcRight(i);

        TreeSet<Integer> set = new TreeSet<Integer>();

        int max = 0;
        for(int i = 0; i < n; i++) {
            int curr = right[i] - left[i];
            if(curr > max) {
                set.clear();
                set.add(left[i]);
                max = curr;
            } else if(curr == max) {
                set.add(left[i]);
            }
        }

        out.println(set.size() + " " + max);
        for (Integer it : set)
            out.print((it + 1) + " ");
    }

    public void run() {
        try {
            if(FILE.isEmpty()) {
                in = new FastScanner(new InputStreamReader(System.in));
                out = new PrintWriter(new OutputStreamWriter(System.out));
            } else {
                in = new FastScanner(new File(FILE + ".in"));
                out = new PrintWriter(new File(FILE + ".out"));
            }

            solve();

            out.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        FastScanner(File f) {
            try {
                br = new BufferedReader(new FileReader(f));
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

        FastScanner(InputStreamReader rd) {
            br = new BufferedReader(rd);
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }
    }

    class Pair<U extends Comparable<U>, V extends Comparable<V>> implements Comparable<Pair<U, V>> {
        U u;
        V v;

        public Pair(U u, V v) {
            this.u = u;
            this.v = v;
        }

        public int hashCode() {
            return (u == null ? 0 : u.hashCode() * 31) + (v == null ? 0 : v.hashCode());
        }

        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;
            Pair<U, V> p = (Pair<U, V>) o;
            return (u == null ? p.u == null : u.equals(p.u)) && (v == null ? p.v == null : v.equals(p.v));
        }

        public int compareTo(Pair<U, V> b) {
            int cmpU = u.compareTo(b.u);
            return cmpU != 0 ? cmpU : v.compareTo(b.v);
        }
    }


    public static void main(String[] args) {
        new Main().run();
    }
}
