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 static java.lang.Math.*;
import static java.lang.System.currentTimeMillis;
import static java.lang.System.exit;
import static java.lang.System.arraycopy;
import static java.util.Arrays.sort;
import static java.util.Arrays.binarySearch;
import static java.util.Arrays.fill;
import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        try {
            if (new File("input.txt").exists())
                System.setIn(new FileInputStream("input.txt"));
        } catch (SecurityException e) {
        }
        new Main().run();
    }

    BufferedReader in;
    PrintWriter out;
    StringTokenizer st = new StringTokenizer("");

    private void run() throws IOException {
        in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        solve();
        in.close();
        out.close();
    }
    
    final int MAXN = 3*100000 + 1;
    int[][] ST;
    int[] a = new int[MAXN];
    int n;
    
    int gcd(int a, int b){return b==0?a:gcd(b,a%b);}
    void initST(){
        int k = 1;
        while( (1 << k) < n )
            k++;
        ST = new int[k+1][MAXN];
        buildST(k);
    }
    void buildST(int k){
        for(int i = 0; i < k; i++)
            for(int j = 0; j < n; j++)
                if(i == 0)
                    ST[i][j] = a[j];
                else{
                    int nj = j + (1 << (i-1));
                    if(nj < n)
                        ST[i][j] = gcd(ST[i-1][j],ST[i-1][nj]);
                    else
                        ST[i][j] = ST[i-1][j];
                }
    }
    
    int gcdL_R(int l, int r){
        int rb = 0;
        while( (1 << rb) <= (r - l) / 2 )
            rb++;
        int res = ST[rb][l];
//      System.err.println(l + " : " + (l + (1 << (rb)) - 1));
        if((1<<rb) != (r-l+1)){
//          System.err.println((r - (1 << (rb)) + 1 ) + " : " + ((r - (1 << (rb))) + (1 << (rb))));
            res = gcd(res,ST[rb][r - (1 << (rb)) + 1]);
        }
        return res;
    }
    
    public void solve() throws IOException{
        n = nextInt();
        for(int i = 0; i < n; i++)
            a[i] = nextInt();
        initST();
//      System.err.println(gcdL_R(1,4));
        TreeSet<Integer> set = new TreeSet<Integer>();
        int maxLen = 0;
        for(int i = 0; i < n; i++){
            int l = i, r = n-1;
            if(gcdL_R(i,r) != a[i]){
                while(r-l > 1){
                    int m = (l+r) >> 1;
                    int _gcd = gcdL_R(i,m);
                    if(_gcd != a[i])
                        r = m;
                    else 
                        l = m;
                }
            } else
                l = r;
//          System.err.println(a[i] +" L:" + i + " R:" + l);
            
            int rr = i, ll = 0;
            if(gcdL_R(ll,rr) != a[i]){
                while(rr - ll > 1){
                    int m = (ll + rr) >> 1;
                    int _gcd = gcdL_R(m,i);
                    if(_gcd != a[i])
                        ll = m;
                    else
                        rr = m;
                }
            } else
                rr = ll;
//          System.err.println(a[i] + " L:" + rr + " R:" + i);
            if(l - rr > maxLen){
                maxLen = l - rr;
                set.clear();
                set.add(rr);
            } else if(l - rr == maxLen){
                if(!set.contains(rr))
                    set.add(rr);
            }           
        }
        out.println(set.size() + " " + maxLen);
        for(int l : set){
            out.print((l+1) + " ");
        }
        out.println();
    }

    void chk(boolean b) {
        if (b)
            return;
        System.out.println(new Error().getStackTrace()[1]);
        exit(999);
    }
    void deb(String fmt, Object... args) {
        System.out.printf(Locale.US, fmt + "%n", args);
    }
    String nextToken() throws IOException {
        while (!st.hasMoreTokens())
            st = new StringTokenizer(in.readLine());
        return st.nextToken();
    }
    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }
    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }
    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
    String nextLine() throws IOException {
        st = new StringTokenizer("");
        return in.readLine();
    }
    boolean EOF() throws IOException {
        while (!st.hasMoreTokens()) {
            String s = in.readLine();
            if (s == null)
                return true;
            st = new StringTokenizer(s);
        }
        return false;
    }
}