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.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;


public class Main {
    static int power(long x,long n,long k){//快速求幂 x^n%k
        long res=1;
        while (n>0){
            if (n%2==0){
                x=(x*x)%k;
                n/=2;
            }else{
                n--;
                res=(res*x)%k;
            }
        }
        return (int)(res%k);
    }
    public static void main(String arg0[]){
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int a[]=new int[n];
        int q[]=new int[n];
        int dpr[]=new int[n];
        int dpl[]=new int[n];for (int i=0;i<n;i++)a[i]=in.nextInt();
        dpl[0]=1;
        for (int i=1;i<n;i++){
            int t=1;
            dpl[i]=1;
            while(i-t>=0&&a[i-t]%a[i]==0){
                dpl[i]=dpl[i-t]+t;
                t=t+dpl[i-t];
            }
        }
        dpr[n-1]=1;
        for (int i=n-2;i>=0;i--){
            int t=1;
            dpr[i]=1;
            while(i+t<n&&a[i+t]%a[i]==0){
                dpr[i]=dpr[i+t]+t;
                t=t+dpr[i+t];
            }
        }
        int max=0;
        for (int i=0;i<n;i++){
            max=Math.max(max, dpl[i]+dpr[i]-1);
        }
        int num=0,len=0;
        for (int i=0;i<n;i++){
            if  (dpl[i]+dpr[i]-1==max){ num++;
                q[len++]=i-dpl[i]+1+1;
            }
        }
    
        Arrays.sort(q,0,num);
        //for (int i=0;i<num;i++){ System.out.println(q[i]);}
        int cu=-1000;len=0;
        for (int i=0;i<num;i++){
            if (q[i]!=cu){
                len++;
                cu=q[i];
            }else{
                cu=q[i];
                q[i]=-1;
            }
        }
        //for (int i=0;i<num;i++){ System.out.println(q[i]);}
        System.out.println(len+" "+(max-1));
        int qi=0;
        for (int i=0;i<num;i++){
              if (q[i]==-1) continue;
                if (qi!=0) System.out.print(" "); else qi=1;
                System.out.print(q[i]);
        }
         System.out.println();
    }
}
