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 problem359D {

    public static int gcd(int a, int b){
        if (b==0)return a;
        return gcd(b, a%b);
    }
    public static void main(String[]args)throws IOException{
        BufferedReader x=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(x.readLine());
        int MAXN=0;//first power of 2 over
        while ((1<<MAXN)<=n){
            MAXN++;
        }
        int[][]min=new int[n][MAXN];
        int[][]gcd=new int[n][MAXN];
        StringTokenizer st=new StringTokenizer(x.readLine());
        for (int i=0; i<n; i++){
            min[i][0]=Integer.parseInt(st.nextToken());
            gcd[i][0]=min[i][0];
        }
        //min and gcd sparse tables
        for (int j=1; j<MAXN; j++){
            for (int i=0; i+(1<<j)-1<n; i++){
                min[i][j]=Math.min(min[i][j-1], min[i+(1<<(j-1))][j-1]);
                gcd[i][j]=gcd(gcd[i][j-1], gcd[i+(1<<(j-1))][j-1]);
            }
        }
        int left=0;
        int right=n;
        while (left<right){//find maximum value that still works
            int mid=(left+right+1)/2;
            int level=0;
            while ((1<<level)<mid+1){
                level++;
            }
            level=Math.max(0, level-1);
            boolean good=false;
            for (int i=0; i+mid<n; i++){
                int cur_min=Math.min(min[i][level], min[i+mid-(1<<level)+1][level]);
                int cur_gcd=gcd(gcd[i][level], gcd[i+mid-(1<<level)+1][level]);
                if (cur_gcd%cur_min==0){
                    good=true;
                    break;
                }
            }
            if (good){
                left=mid;
            }else{
                right=mid-1;
            }
        }
        ArrayList<Integer>ans=new ArrayList<Integer>();
        for (int i=0; i+left<n; i++){
            int level=0;
            while ((1<<level)<left+1){
                level++;
            }
            level=Math.max(0, level-1);
            int cur_min=Math.min(min[i][level], min[i+left-(1<<level)+1][level]);
            int cur_gcd=gcd(gcd[i][level], gcd[i+left-(1<<level)+1][level]);
            if (cur_gcd%cur_min==0){
                ans.add(i);
            }
        }
        System.out.print(ans.size()+" ");
        System.out.println(left);
        StringBuilder sb=new StringBuilder();
        for (int i=0; i<ans.size(); i++){
            sb.append(ans.get(i)+1+" ");
        }
        System.out.println(sb.toString());
    }
}