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 cf209D {
	static int[][] mst;
	static int[][] gcd;
    public static void main(String[] args) throws Exception {
    	// BufferedReader in = new BufferedReader(new FileReader("cf209D.in"));
    	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    	
		int n = Integer.parseInt(in.readLine());
		String[] arr = in.readLine().split(" ");
		
		int[] a = new int[arr.length];
		for(int i = 0; i < a.length; i++) {
			a[i] = Integer.parseInt(arr[i]);
		}
		
		int maxpow = (int) Math.ceil(Math.log(n) / Math.log(2)) + 1;
		mst = new int[maxpow][n];
		gcd = new int[maxpow][n];
		for(int i = 0; i < n; i++) {
			mst[0][i] = a[i];
			gcd[0][i] = a[i];
		}
		for(int i = 1; 1 << i <= n; i++) {
			for(int j = 0; j < n - (1 << i) + 1; j++) {
				gcd[i][j] = gcd(gcd[i - 1][j], gcd[i - 1][j + (1 << i - 1)]);
				mst[i][j] = Math.min(mst[i - 1][j], mst[i - 1][j + (1 << i - 1)]);
			}
		}
		int min = 0;
		int max = n - 1;
		ArrayList<Integer> list = new ArrayList<Integer>();
		while(min < max) {
			int mid = min + max + 1 >> 1;
			ArrayList<Integer> tmp = new ArrayList<Integer>();
			for(int i = 0; i < n - mid; i++) {
				if(q1(i, i + mid) == q2(i, i + mid)) {
					tmp.add(i);
				}
			}
			if(!tmp.isEmpty()) {
				min = mid;
			} else {
				max = mid - 1;
			}
		}
		for(int i = 0; i < n - min; i++) {
			if(q1(i, i + min) == q2(i, i + min)) {
				list.add(i);
			}
		}
		System.out.println(list.size() + " " + min);
		for(int i = 0; i < list.size(); i++) {
			System.out.print(list.get(i) + 1 + (i == list.size() - 1 ? "\n" : " "));
		}
	}

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

	public static int q1(int l, int r) {
		int maxpow = (int) (Math.floor(Math.log(r - l + 1) / Math.log(2)));
		int a = gcd[maxpow][l];
		int b = gcd[maxpow][r - (1 << maxpow) + 1];
		return gcd(a, b);
	}

	public static int q2(int l, int r) {
		int maxpow = (int) (Math.floor(Math.log(r - l + 1) / Math.log(2)));
		int a = mst[maxpow][l];
		int b = mst[maxpow][r - (1 << maxpow) + 1];
		return Math.min(a, b);
	}
}