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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.Random;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Solution{
	
	static int n;
	static int[] a;
	static int[][] sparse;
	static int[] lg;
	
	
	
    public static void main(String[] args) throws IOException {
    	
		
    	FastScanner fs = new FastScanner();
    	PrintWriter out = new PrintWriter(System.out);
    		
    	int tt = 1;
    	while(tt-->0) {
    		
    		
    		n = fs.nextInt();
    		a = fs.readArray(n);
    		
    		sparse = new int[n][20];
    		
    		for(int i=0;i<n;i++) sparse[i][0] = a[i];
    		
    		for(int j=1;j<20;j++) {
    			for(int i=0;i<n && i+(1<<j)-1<n;i++) {
    				sparse[i][j] = gcd(sparse[i][j-1], sparse[i+(1<<(j-1))][j-1]);
    			}
    		}
    		
    		lg = new int[n+1];
    		lg[1] = 0;
    		for(int i=2;i<=n;i++) lg[i] = lg[i/2] + 1;
    		
    		int ans = 0;
    		HashSet<Integer> set = new HashSet<>();
    		
    		for(int i=0;i<n;i++) {
    			int lind = lsearch(i);
    			int rind = rsearch(i);
    			if(rind-lind>ans) {
    				ans = rind-lind;
    				set.clear();
    				set.add(lind+1);
    			}
    			else if(rind-lind==ans) {
    				set.add(lind+1);
    			}
    		}
    		
    		TreeSet<Integer> ts = new TreeSet<>(set);
    		
    		out.println(set.size() + " " +  ans);
    		for(int i: ts) {
    			out.print(i + " ");
    		}
    		out.println();
    		
    		
    		
    		
    	
    		
    		
    		
    	}
    	
    	out.close();
    		
    }
    
    static int lsearch(int ind) {
    	int l = 0, r = ind;
    	while(l<r) {
    		int mid = (l+r)/2;
    		if(query(mid, ind)<a[ind]) {
    			l = mid + 1;
    		}
    		else{
    			r = mid;
    		}
    	}
    	return l;
    }
    
    
    static int rsearch(int ind) {
    	int l = ind, r = n-1;
    	while(l<r) {
    		int mid = (l+r+1)/2;
    		if(query(ind, mid)<a[ind]) {
    			r = mid - 1;
    		}
    		else {
    			l = mid;
    		}
    	}
    	return l;
    }
    
    
    static int query(int l, int r) {
    	int p = lg[r-l];
    	return gcd(sparse[l][p], sparse[r-(1<<p)+1][p]);
    }
    
   
    
    
    static int gcd(int a,int b) {
    	if(b==0) return a;
    	return gcd(b, a%b);
    }
    
   
    
    
    
    
    
    
    
    static final Random random=new Random();
    
    static <T> void shuffle(T[] arr) {
    	int n = arr.length;
    	for(int i=0;i<n;i++	) {
    		int k = random.nextInt(n);
    		T temp = arr[k]; arr[k] = arr[i]; arr[i] = temp;
    	}
    }
    
    	
    static void ruffleSort(int[] a) {
    	int n=a.length;//shuffle, then sort 
    	for (int i=0; i<n; i++) {
    		int oi=random.nextInt(n); int temp=a[oi];
    		a[oi]=a[i]; a[i]=temp;
    	}
    	Arrays.sort(a);
    }
    
    static void ruffleSort(long[] a) {
    	int n=a.length;//shuffle, then sort 
    	for (int i=0; i<n; i++) {
    		int oi=random.nextInt(n); long temp=a[oi];
    		a[oi]=a[i]; a[i]=temp;
    	}
    	Arrays.sort(a);
    }
   
  
    
    static void reverse(int[] arr, int l, int r) {
    	for(int i=l;i<l+(r-l)/2;i++){
    		int temp = arr[i]; arr[i] = arr[r-i+l-1]; arr[r-i+l-1] = temp;
    	}
    }
    
    static void reverse(long[] arr, int l, int r) {
    	for(int i=l;i<l+(r-l)/2;i++){
    		long temp = arr[i]; arr[i] = arr[r-i+l-1]; arr[r-i+l-1] = temp;
    	}
    }
    
    
    static <T> void reverse(T[] arr, int l, int r) {
    	for(int i=l;i<l+(r-l)/2;i++) {
    		T temp = arr[i]; arr[i] = arr[r-i+l-1]; arr[r-i+l-1] = temp;
    	}
    }
    	
    	
    static class FastScanner{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer("");
     
    	public String next(){
    		while(!st.hasMoreElements()){
    			try{
    				st = new StringTokenizer(br.readLine());
    			} catch(IOException e){
    				e.printStackTrace();
    			}
    		}
    		return st.nextToken();
    	}
    		
    	public String nextLine() throws IOException {
    		return br.readLine();
    	}
    		
    	public int nextInt(){
    		return Integer.parseInt(next());
    	}
     
    	public int[] readArray(int n){
    		int[] a = new int[n];
    		for(int i=0;i<n;i++)
    			a[i] = nextInt();
    		return a;
    	}
    		
    	public long nextLong() {
    		return Long.parseLong(next());
    	}
    		
    	public char nextChar() {
    		return next().toCharArray()[0];
    	}
    }
   	
}
