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).
// 11:22
import java.util.*;
import java.io.*;

public class PairOfNumbers {
	public static void main(String[] args) throws IOException {
		BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		n = Integer.parseInt(rd.readLine());
		StringTokenizer st = new StringTokenizer(rd.readLine());
		a = new int[n];
		for(int i=0; i<n; i++)
			a[i] = Integer.parseInt(st.nextToken());
		G = new int[4*n+1];
		T = new int[4*n+1];
		build(1, 0, n-1);
		int size = binSearch(1, n);
		ArrayList<Integer> indices = new ArrayList<Integer>();
		for(int i=0; i<=n-size; i++){
			Pair p = getPair(1, 0, n-1, i, i+size-1);
			if(p.min==p.g)
				indices.add(i+1);
		}
		pw.println(indices.size()+" "+(size-1));
		for(int i=0; i<indices.size(); i++)
			pw.print(indices.get(i)+" ");
		pw.println();
		pw.flush();
	}
	
	
	
	static int binSearch(int L, int R){
		if(L==R)
			return R;
		if(R==L+1)
			return sizeOk(R) ? R : L; 
		int M = (L + R) >> 1;
		return sizeOk(M) ? binSearch(M, R) : binSearch(L, M-1);
	}
	
	static boolean sizeOk(int size){
		for(int i=0; i<=n-size; i++){
			Pair p = getPair(1, 0, n-1, i, i+size-1);
			if(p.min == p.g)
				return true;
		}
		return false;
	}
	
	static Pair getPair(int v, int vL, int vR, int a, int b){
		if(vL==a && vR==b)
			return new Pair(G[v], T[v]);
		int vM = (vL + vR)>>1;
		if(b <= vM)
			return getPair(2*v, vL, vM, a, b);
		if(a > vM)
			return getPair(2*v+1, vM+1, vR, a, b);
		Pair p1 = getPair(2*v, vL, vM, a, vM), p2 = getPair(2*v+1, vM+1, vR, vM+1, b);
		return new Pair(gcd(p1.g, p2.g), Math.min(p1.min, p2.min));
	}
	
	static void build(int v, int vL, int vR){
		if(vL==vR){
			T[v] = G[v] = a[vL];
			return;
		}
		int vM = (vL + vR) >> 1;
		build(2*v, vL, vM);
		build(2*v+1, vM+1, vR);
		T[v] = Math.min(T[2*v], T[2*v+1]);
		G[v] = gcd(G[2*v], G[2*v+1]);
	}
	
	static int gcd(int x, int y){
		if(x==0 || y==0) return x+y;
		return x>y? gcd(y, x%y) : gcd(x, y%x);
	}
	
	static int[] G, T;
	
	static int[] a;
	static int n;
	
}

class Pair{
	public int g, min;
	
	public Pair(int g, int m){
		this.g = g;
		this.min = m;
	}
}
