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.math.BigInteger;
import java.util.*;
import java.util.Collections.*;

import static java.util.Collections.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.math.BigInteger.*;
import static java.lang.Character.*;

public class Main {

    void run(){
//        boolean oj = true;
//        boolean oj = false;


        Locale.setDefault(Locale.US);
        boolean oj = System.getProperty("ONLINE_JUDGE")!=null;

        String fileName = oj? "castle" : "dwarf";
        try {
            if( oj ){
                br = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(new OutputStreamWriter(System.out));
            }
            else{
                br  = new BufferedReader(new FileReader(fileName+".in" ));
                out = new PrintWriter   (new FileWriter(fileName+".out"));
            }
        } catch (Exception e) {
            MLE();
        }
        long tb = System.currentTimeMillis();
        solve();
        if( !oj )
            out.println("TIME: " + (System.currentTimeMillis() - tb) / 1e3) ;
        exit(0);
    }

    BufferedReader br;
    StringTokenizer st;
    PrintWriter out;

    String next(){
        while( st==null || !st.hasMoreElements() ){
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                return null;
            }
        }
        return st.nextToken();
    }
    String nextLine(){
        try {
            return br.readLine();
        } catch (Exception e) {
            return null;
        }
    }
    int nextInt(){ return Integer.parseInt(next()); }
    double nextDouble(){ return Double.parseDouble(next()); }
    long nextLong(){ return Long.parseLong(next()); }

    void exit( int val ){
        out.flush();
        System.exit(val);
    }

    void MLE(){
        int[][] arr = new int[1024*1024][];
        for( int i = 0; i < 1024*1024; ++i )
            arr[i] = new int[1024*1024];
    }

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









    int gcd( int a, int b ){
        return b==0?  a : gcd( b, a%b );
    }

    abstract class F{
        abstract int f(int a, int b);
    }

    class myMin extends F{
        int f(int a, int b){
            return min(a,b);
        }
    }

    class myGCD extends F{
        int f(int a, int b){
            return gcd(a, b);
        }
    }

    int log2( int val ){
        return 31 - Integer.numberOfLeadingZeros(val);
    }

    class SparceTable{
        int[][] tab;
        F fun;

        SparceTable( F _fun ){
            fun = _fun;
            int lim = log2(n);
            tab = new int[n+1][lim+1];
            for( int p = 0; p <= lim; ++p ){
                for( int i = 1; i <= n && i+(1<<p)-1 <= n; ++i ){
                    if( p == 0 ){
                        tab[i][p] = arr[i];
                    }
                    else{
                        tab[i][p] = fun.f(
                        tab[i][p-1], tab[i+(1<<(p-1))][p-1] );
                    }
                }
            }
        }

        int qwer( int l, int r ){
            int p = log2( r - l + 1 );
            return fun.f( tab[l][p], tab[r-(1<<p)+1][p] );
        }

    }

    boolean OK( int l, int r ){
        return ST_GCD.qwer(l,r) == ST_Min.qwer(l,r);
    }

    int bsL( int i ){ // m -> min
        int l = 1, r = i;
        while( l+2 <= r ){
            int m = (l + r) / 2;
            if( OK(m,i) ) r = m;
            else l = m;
        }
        if( OK(l,i) ) return l;
        if( OK(r,i) ) return r;
        MLE();
        return -1;
    }

    int bsR( int i ){ // m -> max
        int l = i, r = n;
        while( l+2 <= r ){
            int m = (l + r) / 2;
            if( OK(i,m) ) l = m;
            else r = m;
        }
        if( OK(i,r) ) return r;
        if( OK(i,l) ) return l;
        MLE();
        return -1;
    }

    int n;
    int[] arr;
    int delta;
    TreeSet<Integer> ans;
    SparceTable ST_Min, ST_GCD;

    void solve(){
//        deb();


        n = nextInt();
        arr = new int[n+1];
        for( int i = 1; i <= n; ++i )
            arr[i] = nextInt();
        ST_Min = new SparceTable(new myMin());
        ST_GCD = new SparceTable(new myGCD());

        delta = -1;
        ans = new TreeSet<>();
        for( int i = 1; i <= n; ++i ){
            int l = bsL(i),
                r = bsR(i);
            if( delta < r - l ){
                delta = r - l;
                ans = new TreeSet<>();
            }
            if( delta == r - l )
                ans.add( l );
        }
        out.println( ans.size() +" "+ delta );
        for( int L : ans ) out.print( " " + L );
        out.println();
        /**/
    }


    void deb(){
        for( int i = 0; i <= 50; ++i )
            out.printf( "%3d %3d\n", i, log2(i) );
    }


}