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
{
	public static void main(String [] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(reader.readLine());
		int [] array = new int[n];
		StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
		for(int i = 0 ; i < n ; i++)
			array[i] = Integer.parseInt(tokenizer.nextToken());

		SegmentTree min = new SegmentTree(array, 1000000000);
		SegmentTree gcd = new SegmentTree(array, 0);

		int lb = 0;
		int ub = n+1;
		while(ub - lb > 1)
		{
			int mid = (lb + ub)/2;
			if(count(min, gcd, mid, n) != 0)
				lb = mid;
			else
				ub = mid;
		}

		writer.println(count(min, gcd, lb, n)+" "+(lb));
		int [] res = new int[count(min, gcd, lb, n)];
		int at = 0;
		for(int left = 0 ; left + lb < n ; left++)
			if(min.get(left, left+lb) == gcd.get(left, left+lb))
				res[at++] = left+1;
		writer.print(res[0]);
		for(int i = 1 ; i < at ; i++)
			writer.print(" "+res[i]);
		writer.println();

		writer.flush();
		writer.close();

	}

	private static int count(SegmentTree min, SegmentTree gcd, int len, int n)
	{
		int res = 0;
		for(int left = 0 ; left + len < n ; left++)
			if(min.get(left, left+len) == gcd.get(left, left+len))
				res++;

		return res;
	}
}

class SegmentTree
{
	private int [][] tree;
	private int n;
	private int [] array;
	private int IDENTITY;
	public SegmentTree(int [] array, int identity)
	{
		IDENTITY = identity;
		int N = 2*Integer.highestOneBit(array.length);
		n = 0;
		while((1<<n) < Integer.highestOneBit(N))
			n++;
		this.array = array.clone();

		tree = new int[N][n+1];
		for (int x = 0; x < array.length; x++)
			tree[x][0] = array[x];
		for (int y = 1; y <= n; y++)
			for (int x = 0; x < N; x+=(1<<y))
			{
				if(identity == 0)
					tree[x][y] = gcd(tree[x][y - 1], tree[x + (1 << (y - 1))][y - 1]);
				else
					tree[x][y] = Math.min(tree[x][y - 1], tree[x + (1 << (y - 1))][y - 1]);
			}
	}

	void set(int x, int v)
	{
		tree[x][0] = array[x] = v;
		for (int y = 1; y <= n; y++)
		{
			int xx = x-(x&((1<<y)-1));
			if(IDENTITY == 0)
				tree[xx][y] = gcd(tree[xx][y - 1], tree[xx + (1 << (y - 1))][y - 1]);
			else
				tree[xx][y] = Math.min(tree[xx][y - 1], tree[xx + (1 << (y - 1))][y - 1]);
		}
	}

	int get(int i, int j)
	{
		int res = IDENTITY, h = 0; j++;
		while (i+(1<<h) <= j)
		{
			while ((i&((1<<(h+1))-1)) == 0 && i+(1<<(h+1)) <= j) h++;
			if(IDENTITY == 0)
				res = gcd(res, tree[i][h]);
			else
				res = Math.min(res, tree[i][h]);
			i += (1<<h);
		}
		while (i < j)
		{
			while (i+(1<<h) > j) h--;
			if(IDENTITY == 0)
				res = gcd(res, tree[i][h]);
			else
				res = Math.min(res, tree[i][h]);
			i += (1<<h);
		}
		return res;
	}

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