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 D implements Runnable {

	private void solve() throws IOException {
		int n = nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = nextInt();
		SparseTable t = new SparseTable(a);
		int best = 0, cnt = 0;
		int[] ans = new int[n];
		for (int i = 0; i < n; i++) {
			int l1 = -1, r1 = i;
			while (r1 - l1 > 1) {
				int m = (l1 + r1) >> 1;
				int cur = t.gcd(m, i, 0);
				if (cur == a[i]) 
					r1 = m; 
				else
					l1 = m;
			}
			int l2 = i, r2 = n;
			while (r2 - l2 > 1) {
				int m = (l2 + r2) >> 1;
				int cur = t.gcd(i, m, 0);
				if (cur == a[i]) 
					l2 = m; 
				else
					r2 = m;
			}
			int cur = l2 - r1;
			if (cur == best) {
				if (cnt == 0) 
					ans[cnt++] = r1;
				else if (ans[cnt - 1] != r1)
					ans[cnt++] = r1;
			}
			if (cur > best) {
				best = cur;
				cnt = 1;
				ans[0] = r1;
			}
		}
		println(cnt, best);
		for (int i = 0; i < cnt; i++) {
			if (i != 0) print(' ');
			print(ans[i] + 1);
		}
	}
	
	class SparseTable {
		private int n;
		private int[] two, log;
		private int[][] t;

		int gcd(int a, int b) {
			return (a == 0) ? b : gcd(b % a, a);
		}
		
		SparseTable(int[] a) {
			two = new int[31];
			two[0] = 1;
			for (int i = 1; i < 31; i++)
				two[i] = two[i - 1] * 2;

			n = a.length;

			log = new int[n + 1];
			for (int i = 2; i <= n; i++)
				log[i] = log[i / 2] + 1;

			t = new int[n][log[n] + 1];
			for (int j = 0; j <= log[n]; j++)
				for (int i = 0; i < n; i++)
					if (j == 0)
						t[i][j] = a[i];
					else {
						t[i][j] = t[i][j - 1];
						if (i + two[j - 1] < n)
							t[i][j] = gcd(t[i][j],
									t[i + two[j - 1]][j - 1]);
					}

		}

		int gcd(int l, int r, int tmp) {
			int j = log[r - l + 1];
			return gcd(t[l][j], t[r - two[j] + 1][j]);
		}
	}
	
	class SegmentTree {
		int n;
		int[] t;
		
		SegmentTree(int[] a) {
			this.n = a.length;
			t = new int[n * 4];
			buildTree(a, 1, 0, n - 1);
		}
		
		int gcd(int a, int b) {
			return (a == 0) ? b : gcd(b % a, a);
		}
		
		void buildTree(int[] a, int v, int l, int r) {
			if (l == r) t[v] = a[l]; else {
				int m = (l + r) >> 1;
				buildTree(a, v * 2, l, m);
				buildTree(a, v * 2 + 1, m + 1, r);
				t[v] = gcd(t[v * 2], t[v * 2 + 1]);
			}
		}
		
		int gcd(int v, int tl, int tr, int l, int r) {
			if (l > r) return 0;
			if (tl == l && tr == r) return t[v];
			int tm = (tl + tr) >> 1;
			int a = gcd(v * 2, tl, tm, l, Math.min(r, tm));
			int b = gcd(v * 2 + 1, tm + 1, tr, Math.max(tm + 1, l), r);
			return gcd(a, b);
		}
	}

	public static void main(String[] args) {
		new D().run();
	}

	BufferedReader reader;
	StringTokenizer tokenizer;
	PrintWriter writer;

	public void run() {
		try {
			reader = new BufferedReader(new InputStreamReader(System.in));
			writer = new PrintWriter(System.out);
			solve();
			writer.close();
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(261);
		}
	}

	void halt() {
		writer.close();
		System.exit(0);
	}

	void print(Object... objects) {
		for (int i = 0; i < objects.length; i++) {
			if (i != 0)
				writer.print(' ');
			writer.print(objects[i]);
		}
	}

	void println(Object... objects) {
		print(objects);
		writer.println();
	}

	String nextLine() throws IOException {
		return reader.readLine();
	}

	String nextToken() throws IOException {
		while (tokenizer == null || !tokenizer.hasMoreTokens())
			tokenizer = new StringTokenizer(nextLine());
		return tokenizer.nextToken();
	}

	int nextInt() throws NumberFormatException, IOException {
		return Integer.parseInt(nextToken());
	}

	long nextLong() throws NumberFormatException, IOException {
		return Long.parseLong(nextToken());
	}

	double nextDouble() throws NumberFormatException, IOException {
		return Double.parseDouble(nextToken());
	}
}
