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 c{ 
static PrintWriter out = new PrintWriter(System.out);
static int STM[][];
static int STG[][];
static int Log[];
static void fun(int n,int k,int a[]){
                            for (int i = 0; i <n; i++)
                               {
                                 STM[i][0] = a[i];
                                 STG[i][0] = a[i];
                               }
                            for (int j = 1; j <k; j++)
                               for (int i = 0; (i+(1 << j))<=n; i++)
                                     {
                                       STM[i][j] = Math.min(STM[i][j-1], STM[i + (1 << (j - 1))][j - 1]);
                                       STG[i][j] = gcd(STG[i][j-1], STG[i + (1 << (j - 1))][j - 1]);
                                    }
                    } 
static boolean ok(int m,int n){

            int i1=0,i2=m-1;
               while(i2<n){
                           int j=Log[i2-i1+1];
                           int min = Math.min(STM[i1][j],STM[i2-(1<<j)+1][j]);
                           int g = gcd(STG[i1][j],STG[i2-(1<<j)+1][j]);
                           if(min==g)
                              return true;
                              i1++; i2++;
              }
                    return false;
}
public static void main(String[] args) 
{ 
     int n = ni();
     int a[] = new int[n];
     for(int i=0;i<n;i++)
         a[i] = ni();

     int k = (int)(Math.log(n)/Math.log(2))+1;
      STM = new int[n][k];
      STG = new int[n][k];
      Log = new int[n+1];

     fun(n,k,a);
        Log[1] = 0;
       for (int i = 2; i <=n; i++)
           Log[i] = Log[i/2]+1;
       int l=1,r=n+1;
         while((r-l)>1){
             int m = (l+r)/2;
             if(ok(m,n))
                l=m;
             else
                r=m;
        }
    ArrayList<Integer> arr = new ArrayList();
    int i1=0,i2=l-1,ans=0;

      while(i2<n){

                 int j=Log[i2-i1+1];
                           int min = Math.min(STM[i1][j],STM[i2-(1<<j)+1][j]);
                           int g = gcd(STG[i1][j],STG[i2-(1<<j)+1][j]);
                           if(min==g){
                               arr.add(i1+1);
                               ans++;
                            }
              i1++; i2++;
      }
         out.println(ans+" "+(l-1));
         for(Integer i: arr)
               out.print(i+" ");
         out.flush();

}

static long mod = 1000000007;
static void fact(long a[]){
         a[0]=1;
         for(int i=1;i<a.length;i++)
                a[i] = (i*a[i-1])%mod;
}
static int gcd(int a,int b){

  if(b%a==0) return a;
  return gcd(b%a,a);
}
static long pow(long a,long b,long mod){

long ans=1;
while(b>0){
if(b%2==1)
    ans = (ans*a)%mod;
    b=b/2;
    a=(a*a)%mod;
}
   return ans;
}  
    static FastReader sc=new FastReader(); 
 
      static int ni(){
                 int x = sc.nextInt();
                 return(x);
        }
      static long nl(){
              long x = sc.nextLong();
              return(x);
         }
      static String n(){
                 String str = sc.next();
                     return(str);
       }
     static String ns(){
                 String str = sc.nextLine();
                   return(str);
      }
     static double nd(){
               double d = sc.nextDouble();
                 return(d);
       }
  static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
}