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.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class PairsOfNumbers {

	public static int n;
	public static int maxValue;
	
	public static long[] numbers;
	
	public static SparseTable gcdtree, lowesttree;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		
		int x = (int) (Math.ceil(Math.log(n) / Math.log(2)));
		 
        //Maximum size of segment tree
        maxValue = 2 * (int) Math.pow(2, x) - 1;

        maxValue = Math.max(2 * n, maxValue);
        
		numbers = new long[n];
		
		StringTokenizer tokenizer = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			numbers[i] = Integer.parseInt(tokenizer.nextToken());
		}
		
		br.close();
		
		gcdtree = new SparseTable(numbers, new GCDCombiner());
		lowesttree = new SparseTable(numbers, new Combiner() {

			@Override
			public long combine(long i, long i2) {
				return Math.min(i, i2);
			}
			
			@Override
			public long getFillValue() {
				return Long.MAX_VALUE / 4;
			}
			
		});

		/*
		 * Idea: Use a binary tree to store gcd data. This idea comes from the fact that
		 * you can store the gcd of every x numbers and calculate in precomputed blocks
		 * rather than individually.
		 * */

/*		for(int i = 0; i < n; i++) {
			int length = dp[i];
			long gcd = gcdtree.query(i - dp[i], i);
			while(true) {
				int current = i - length;
				if(current < 0)
					break;
				int otherstart = current - dp[current], otherend = current;
				long newgcd = gcd(gcd, gcdtree.query(otherstart, otherend));
				if(newgcd == 1) {
					break;
				}
				gcd = newgcd;
				length = i - otherstart;
			}
			if(length > totalLength) {
				totalLength = length;
			}
		}*/
		

		//Binary search for length
		int min = 0, max = n + 1;
		int lastWorking = -1;
		
		while(min != max) {
			int mid = (min + max) / 2;
			
			//If the target works, try to go higher
			if(evaluate(mid)) {
				lastWorking = mid;
				min = mid + 1;
			}else{ //Otherwise, go lower
				max = mid;
			}
		}
		
		int length = lastWorking;
		int number = 0;
		
		for(int l = 0; l <= n - length; l++){
			long gcd = gcdtree.query(l, l + length - 1);
			long lowest = lowesttree.query(l, l + length - 1);
			if(gcd == lowest) {
				number++;
			}
		}
		
		System.out.println(number + " " + (length - 1));
		
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int counter = 0;
		for(int l = 0; l <= n - length; l++){
			long gcd = gcdtree.query(l, l + length - 1);
			long lowest = lowesttree.query(l, l + length - 1);
			if(gcd == lowest) {
				if(counter > 0)
					bw.append(' ');
				
				counter++;
				bw.append(String.valueOf(l + 1));
			}
		}
		bw.append('\n');
		bw.close();
	}
	
	public static boolean evaluate(int totalLength) {
		for(int l = 0; l <= n - totalLength; l++){
			long gcd = gcdtree.query(l, l + totalLength - 1);
			long lowest = lowesttree.query(l, l + totalLength - 1);
			if(gcd == lowest) {
				return true;
			}
		}
		return false;
	}
	
	public static long lcm(long a, long b) {
		return (a * b) / gcd(a, b);
	}

	// Function to return
	// gcd of a and b
	public static long gcd(long a, long b) {
	    if (a == 0){
	        return b;
	    }
	    return gcd(b % a, a);
	}
	
	public static class SparseTable {
		
		public long[][] table;
		
		public Combiner combiner;
		
		public SparseTable(long[] elements, Combiner combiner) {
			this.combiner = combiner;
			
			table = new long[n][(int)Math.ceil(Math.log(n) / Math.log(2)) + 1];
			
			for(int i = 0; i < n; i++) {
				table[i][0] = elements[i];
			}
			
			// Compute values from smaller to bigger intervals
	        for (int j = 1; (1 << j) <= n; j++) {
	     
	            // Compute minimum value for all intervals with
	            // size 2^j
	            for (int i = 0; (i + (1 << j) - 1) < n; i++) {
	     
	                // For arr[2][10], we compare arr[lookup[0][7]] 
	                // and arr[lookup[3][10]]
	            	table[i][j] = combiner.combine(table[i][j - 1], table[i + (1 << (j - 1))][j - 1]);
	            }
	        }
		}
		
		public long query(int l, int r) {
			int j = (int)(Math.log(r - l + 1) / Math.log(2));
			return combiner.combine(table[l][j], table[r - (1 << j) + 1][j]);
		}
	}
	
	public static class SegmentTree {
		public long[] tree;
		public Pair[] interval;
		
		public Combiner combiner;
		
		public SegmentTree(long[] elements, Combiner combiner) {
			this.combiner = combiner;
			
			tree = new long[maxValue];
			interval = new Pair[maxValue];
			
			if(combiner.getFillValue() != 0)
				Arrays.fill(tree, combiner.getFillValue());
			
			for(int i = 0; i < maxValue; i++){
				interval[i] = new Pair(-1, -1);
			}

			init(1, 0, n - 1);
			
			for(int i = 0; i < n; i++) {
				update(i, 1, elements[i]);
			}
		}
		
		public long queryInternal(int i, int l, int r){
			//if not intersecting
			if(interval[i].second < l || interval[i].first > r){
				return combiner.getFillValue();
			}
			//if completely intersecting
			if(interval[i].first >= l && interval[i].second <= r){
				return tree[i];
			}
			//if partially intersecting
			return combiner.combine(queryInternal(2 * i, l, r), queryInternal(2 * i + 1, l, r));
		}

		public long query(int l, int r){
			return queryInternal(1, l, r);
		}

		public void update(int index, int i, long item){
			if(i >= maxValue)
				return;

			if(index < interval[i].first || index > interval[i].second){
				return;
			}

			tree[i] = combiner.combine(tree[i], item);

			update(index, 2 * i, item);
			update(index, 2 * i + 1, item);
		}

		public void init(int i, int l, int r) {
			interval[i] = new Pair(l, r);
			if (l == r)	{
				return;
			}
			int m = (l + r) / 2;
			init(2 * i, l, m);
			init(2 * i + 1, m + 1, r);
		}
	}
	
	public static class GCDCombiner extends Combiner {
		
		@Override
		public long combine(long i, long i2) {
			return gcd(i, i2);
		}
		
		@Override
		public long getFillValue() {
			return 0;
		}
		
	}
	
	public static abstract class Combiner {
		public abstract long combine(long i, long i2);
		public abstract long getFillValue();
	}
	
	public static class Pair {
		public int first, second;
		public Pair(int a, int b) {
			this.first = a;
			this.second = b;
		}
	}

}