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


public class Simon_209D {

	/**
	 * @param args
	 */
	 static MinTree minT;
     static GcdTree gcdT;
     static Integer n;
     static MinSparseTable st;
     static GcdSparseTable gcdst;
     static int arr[];
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
        n = in.nextInt();
        minT = new MinTree();
        gcdT = new GcdTree();
        arr = new int[n];
        for(int i = 0; i < n; i++){
        	int v = in.nextInt();
        	arr[i] = v;
        }
        st = new MinSparseTable(arr);
        gcdst = new GcdSparseTable(arr);
        //System.out.println("min = " + minT.query(0, n-1));
       // System.out.println("gcd = " + gcdst.gcdPos(3, 1));
        
        // bin search for interval length
        int lo = 1;
        int hi = n;
        int mid = 0;
        while (hi - lo > 1) {
        	
            mid = lo + (hi - lo) / 2;
            if (ok(mid)){
            	lo = mid;
            }
            else hi = mid;
        }
        //System.out.println("lo = " + lo +" hi = " + hi + " mid = " + mid);
        if(ok(lo)) {
        	mid = lo;
        	if(ok(mid+1)){
        		mid++;
        		if(ok(mid+1)){
            		mid++;
            		if(ok(mid+1)){
                		mid++;
                	}
            	}
        	}
        }
        
        //System.out.println("lo = " + lo +" hi = " + hi + " mid = " + mid + " found = "+ found);
        //finding intervals:
        if(mid > 1){
        	ArrayList<Integer> start = new ArrayList<Integer>();
            for(int i = 0; i < n; i++){
            	if(i + mid -1 < n){
    				if(arr[st.minPos(i, i + mid -1)] == gcdst.gcdInInterval(i, i + mid-1)){
    					start.add(i+1);
    					//System.out.println("adding");
    				}
            	}
            }
            System.out.println(start.size() + " " + (mid-1));
            for(Integer a : start){
            	System.out.print(a+ " ");
            }
        } else {
        	System.out.println(n + " " +0);
        	for(int i = 1; i <= n; i++){
        		System.out.print(i + " ");
        	}
        	System.out.println();
        }
        
        
	}
	static boolean ok(int length){
		//System.out.println("length = " + length);
		boolean ok = false;
		for(int i = 0; i < n; i++){
			if(i + length -1 < n){
				if(gcdst.gcdInInterval(i, i + length-1) == arr[st.minPos(i, i + length -1)]){
					ok = true;
					//System.out.println("True from " + i + " to " + (i + length -1));
					break;
				} else {
					//System.out.println("not from " + i + " to " + (i + length -1));
				}
			}
		}
		return ok;
	}
	
	static class GcdSparseTable {

		int[] logTable;
		long tab[][];
		int[] a;

		public GcdSparseTable(int[] a) {
			this.a = a;
			int n = a.length;
			
			logTable = new int[n + 1];
			for (int i = 2; i <= n; i++){
				logTable[i] = logTable[i >> 1] + 1;
			}
				
			int k = logTable[n] + 1;
			tab =  new long[n][k];	
			
			for(int i = 0; i < n; i++) {
                tab[i][0] = a[i];
            }

			for(int j = 1; j < k; j++) {
	           for(int i = 0; i + (1 << j) <= n; i++) {
	                int tv = i + (1 << (j - 1));
					long x = tab[i][j - 1];
					long y = tab[tv][j - 1];
	                tab[i][j] = gcd(x, y);
	            }
	        }
		}
		 // GCD in interval [l, r)
		public long gcdInInterval(int l, int r) {
			int k = logTable[r - l];
			long x = tab[l][k];
			long y = tab[r - (1 << k) + 1][k];
			return gcd(y, x);
		}
	}
	
	static class MinSparseTable {

		int[] logTable;
		int[][] tab;
		int[] a;

		public MinSparseTable(int[] a) {
			this.a = a;
			int n = a.length;

			logTable = new int[n + 1];
			for (int i = 2; i <= n; i++)
				logTable[i] = logTable[i >> 1] + 1;

			int k = logTable[n] + 1;
			tab = new int[n][k];

			for (int i = 0; i < n; ++i)
				tab[i][0] = i;

			for(int j = 1; j < k; j++) {
				for (int i = 0; i + (1 << j) <= n; i++) {
	                int tv = i + (1 << (j - 1));
					int x = tab[i][j - 1];
					int y = tab[tv][j - 1];
					tab[i][j] = a[x] <= a[y] ? x : y;
				}
			}
		}

		public int minPos(int l, int r) {
			int k = logTable[r - l];
			int x = tab[l][k];
			int y = tab[r - (1 << k) + 1][k];
			return a[x] <= a[y] ? x : y;
		}
	}
	
	static class GcdTree {
		//Space used is offset,offset + size of table
		private int OFFSET = 1350000;
		private long tree[];	

		// Add v to cell i. For max in interval in comments
		public void update(int i, int v) {
		    i += OFFSET;
		    tree[i] = v;
		    i /= 2;
		    while(i > 0) {
		        tree[i] = gcd(tree[2*i], tree[2*i+1]);
		        i /= 2;
		    }
		}

		// Get sum in interval l (inclusive) to r (inclusive)
		public long query(int l, int r) {
		    long result = 0;
		    l += OFFSET - 1; r+= OFFSET+1;
		    while(l/2 != r/2) {
		        if(l%2 == 0) result = gcd(result, tree[l^1]);
		        if(r%2 == 1) result = gcd(result, tree[r^1]);
		        l /= 2; r /= 2;
		    }
		    return result;
		}
		
		public GcdTree(){
			tree = new long[2*OFFSET];
		}
	}
	
	static class MinTree {
		//Space used is offset,offset + size of table
		private int OFFSET = 1350000;
		private int tree[];	

		// Add v to cell i. For max in interval in comments
		public void update(int i, int v) {
		    i += OFFSET;
		    tree[i] = v;
		    i /= 2;
		    while(i > 0) {
		        tree[i] = Math.min(tree[2*i], tree[2*i+1]);
		        i /= 2;
		    }
		}

		// Get sum in interval l (inclusive) to r (inclusive)
		public int query(int l, int r) {
		    int result = Integer.MAX_VALUE/2;
		    l += OFFSET - 1; r+= OFFSET+1;
		    while(l/2 != r/2) {
		        if(l%2 == 0) result = Math.min(result, tree[l^1]);
		        if(r%2 == 1) result = Math.min(result, tree[r^1]);
		        l /= 2; r /= 2;
		    }
		    return result;
		}
		
		public MinTree(){
			tree = new int[2*OFFSET];
		}
	}
	
	public static long gcd(long a, long b){
		if(a < b){
			long temp = a;
			a = b;
			b = temp;
		}
		if(b == 0) return a;
		return gcd(b, a % b);
	}

}
