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.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.Map;
import java.util.Random;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class solver {
    
    BufferedReader in;
    PrintWriter out;
    StringTokenizer tok;
    
    static final boolean OJ = System.getProperty("ONLINE_JUDGE") != null;
    
    void init() throws FileNotFoundException{
        if (OJ){
          in = new BufferedReader(new InputStreamReader(System.in));
          out = new PrintWriter(System.out);
//            in = new BufferedReader(new FileReader("log.in"));
//            out = new PrintWriter("log.out");
        }else{
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter("output.txt");
        }
    }
    
    String readString() throws IOException{
        while (tok == null || !tok.hasMoreTokens()){
            tok = new StringTokenizer(in.readLine()," :");
        }
        return tok.nextToken();
    }
    
    int readInt() throws NumberFormatException, IOException{
        return Integer.parseInt(readString());
    }
    
    double readDouble() throws NumberFormatException, IOException{
        return Double.parseDouble(readString());
    }
    
    long readLong() throws NumberFormatException, IOException{
        return Long.parseLong(readString());
    }
    long time;
    void run(){
        try{
            time = System.currentTimeMillis();
            init();
            solve();
            System.err.println(System.currentTimeMillis() - time);
            out.close();
            in.close();
        }catch (Exception e){
            e.printStackTrace();
        }
    }
    
    int gcd(int a, int b){
        if (a == 0) return b;
        return gcd(b % a, a);
    }
    
    int[][] gst;
    int[][] mst;
    int[] a;
    int d = 20;
    int n;
    
    
    void makeTables(){
        gst = new int[n][d];
        mst = new int[n][d];
        for (int i=0;i<n;i++){
            gst[i][0] = mst[i][0] = a[i];
        }
        for (int i=1;i<d;i++){
            int delta = 1 << (i-1);
            for (int j=0;j<n;j++){
                if (j + delta >= n) break;
                gst[j][i] = gcd(gst[j][i-1], gst[j+delta][i-1]);
                mst[j][i] = Math.min(mst[j][i-1], mst[j+delta][i-1]);
            }
        }       
    }
    
    boolean check(int l, int r, int lg){
        int len = r - l + 1;
        int gcd = gcd(gst[l][lg],gst[r-(1<<lg) + 1][lg]);
        int min = Math.min(mst[l][lg], mst[r-(1<<lg) + 1][lg]);
        return gcd == min;
    }
        
    boolean check(int len){
        int lg = log2(len);
        for (int i=0;i<n;i++){
            if (i+len-1 >=n) break;
            if (check(i,i+len-1,lg)) {
                return true;
            }
        }
        return false;
    }
    
    int log2(int x){
        return (int)(Math.log(x) / Math.log(2));
    }
    
    void solve() throws NumberFormatException, IOException{
        n = readInt();
        a = new int[n];
        for (int i=0;i<n;i++) a[i] = readInt();
        makeTables();
        int l = 1;
        int r = n;
        int ans = 0;
        while (l<=r){
            int mid = (l+r)/2;
            if (check(mid)){
                ans = mid;
                l = mid+1;
            }else{
                r = mid-1;
            }
        }
        ArrayList<Integer> answer = new ArrayList<Integer>(); 
        int lg = log2(ans);
        for (int i=0;i<n;i++){
            if (i+ans-1 >=n) break;  
            if (check(i,i+ans-1,lg)){
                answer.add(i+1);
            }
        }
        out.println(answer.size()+" "+(ans-1));
        for (int y : answer) out.print(y+" ");
    }

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

}