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.util.*;
import java.io.*;
import static java.lang.System.in;

public class Main {
    static int[][] RMQ,GCD;
    static int n,m;
    static TreeMap<Integer,Integer> dic = new TreeMap<>();
    public static void main(String[] args)throws IOException {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int[] a = new int[n];
        for(int i=0;i<n;i++) a[i]=sc.nextInt();
        for(int i=0;i<20;i++) dic.put(1<<i,i);
        Map.Entry<Integer,Integer> size = dic.floorEntry(n);
        m = size.getValue();
        RMQ = new int[n][m+1]; GCD = new int[n][m+1]; // 2^20 = 1.05e6
        iniGCD(a); iniRMQ(a);
        // ini TreeMap to help find log2 more precisely

        int lo = 1, hi = n+1,mid;
        while(hi>lo+1){
            mid = (hi+lo)>>1;
            if(check(mid)) lo = mid;
            else hi = mid;
        }
        int cnt = 0;
        ArrayList<Integer> start = new ArrayList<>();
        for(int i=0;i+lo<=n;i++){
            if(!getRMQ_GCD(i,i+lo-1)) continue;
            cnt++;
            start.add(i+1);
        }
        PrintWriter out = new PrintWriter(System.out);
        out.println(Integer.toString(cnt)+" "+Integer.toString(lo-1));
        for(int w:start){
            out.print(Integer.toString(w)+" ");
        }
        out.flush();
    }
    static boolean check(int len){
        for(int i=0;i+len<=n;i++){
            if(getRMQ_GCD(i,i+len-1)) return true;
        }
        return false;
    }
    static boolean getRMQ_GCD(int a, int b){
        // flag = true means we want to get RMQ, otherwise get gcd
        if(a==b) return true;
        Map.Entry<Integer,Integer> cur = dic.floorEntry(b-a+1);
        int k = cur.getValue();
        int min = Math.min(RMQ[a][k],RMQ[b-(1<<k)+1][k]);
        int gcd = getGCD(GCD[a][k],GCD[b-(1<<k)+1][k]);
        return min==gcd;
    }
    static void iniRMQ(int[] a){
        for(int i=0;i<n;i++) RMQ[i][0] = a[i];
        for(int k=1;k<=m;k++){
            for(int i=0;i+(1<<k)-1<n;i++){
                RMQ[i][k] = Math.min(RMQ[i][k-1],RMQ[i+(1<<(k-1))][k-1]);
            }
        }
    }
    static void iniGCD(int[] a){
        for(int i=0;i<n;i++) Arrays.fill(GCD[i],1);
        for(int i=0;i<n;i++) GCD[i][0] = a[i];
        for(int k=1;k<=m;k++){
            for(int i=0;i+(1<<k)-1<n;i++){
                GCD[i][k] = getGCD(GCD[i][k-1],GCD[i+(1<<(k-1))][k-1]);
            }
        }
    }
    static int getGCD(int a, int b){
        int c;
        if(a<b){
            c = a; a = b; b = c;
        }
        while(a%b!=0){
            c = b; b = a%b; a = c;
        }
        return b;
    }
}