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.IOException;
import java.io.PrintWriter;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

import static java.lang.Integer.max;
import static java.lang.Math.floor;
import static java.lang.Math.log;

public class C359D {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        IntStream.range(0, n).forEach(i -> a[i] = sc.nextInt());
        sc.close();

        PrintWriter out = new PrintWriter(System.out);
        Set<Pair> results = solve(a);
        out.println(results.size() + " " + (results.iterator().next().getSpan() - 1));
        out.println(results.stream().map(Pair::getL).sorted().map(String::valueOf).collect(Collectors.joining(" ")));
        out.close();
    }

    private static Set<Pair> solve(int[] a) {
        Set<Pair> optimalPairs = new HashSet<>();

        int[][] gcdSparse = getSparseTable(a);
        for (int i = 0; i < a.length; i++) {
            int j = binarySearchRight(i, a.length - 1, a[i], gcdSparse);
            int k = binarySearchLeft(0, i, a[i], gcdSparse);
            optimalPairs = updatePairs(optimalPairs, j, k);
        }

        return optimalPairs;
    }

    private static Set<Pair> updatePairs(Set<Pair> optimalPairs, int high, int low) {
        Pair candidate = new Pair(low + 1, high + 1);
        if (optimalPairs.isEmpty()) {
            optimalPairs.add(candidate);
        } else {
            int currentSpan = high - low + 1;
            int currentMaxSpan = optimalPairs.iterator().next().getSpan();
            if (currentMaxSpan < currentSpan) {
                optimalPairs = new HashSet<>();
                optimalPairs.add(candidate);
            } else if (currentMaxSpan == currentSpan) {
                optimalPairs.add(candidate);
            }
        }
        return optimalPairs;
    }

    private static int binarySearchRight(int low, int high, int target, int[][] gcdSparse) {
        if (low == high) return low;
        if (low == high - 1) {
            if (gcdSparse[low][1] % target == 0) return high;
            else return low;
        }

        int mid = (low + high) / 2;
        if (compatibleRange(low, mid, target, gcdSparse)) {
            return binarySearchRight(mid, high, target, gcdSparse);
        } else {
            return binarySearchRight(low, mid - 1, target, gcdSparse);
        }
    }

    private static int binarySearchLeft(int low, int high, int target, int[][] gcdSparse) {
        if (low == high) return low;
        if (low == high - 1) {
            if (gcdSparse[low][1] % target == 0) return low;
            else return high;
        }

        int mid = (low + high) / 2;
        if (compatibleRange(mid, high, target, gcdSparse)) {
            return binarySearchLeft(low, mid, target, gcdSparse);
        } else {
            return binarySearchLeft(mid + 1, high, target, gcdSparse);
        }
    }

    private static boolean compatibleRange(int low, int high, int target, int[][] gcdSparse) {
        return gcdOfRange(low, high, gcdSparse) % target == 0;
    }

    private static int gcdOfRange(int low, int high, int[][] gcdSparse) {
        int k = (int) floor(log(high - low + 1) / log(2));
        int start = max(0, high - (1 << k) + 1);
        return gcd(gcdSparse[low][k], gcdSparse[start][k]);
    }

    private static int[][] getSparseTable(int[] a) {
        int n = a.length;
        int sparseLen = (int) floor(log(n) / log(2)) + 1;
        int[][] sparse = new int[n][sparseLen];

        for (int i = 0; i < n; i++) {
            sparse[i][0] = a[i];
        }


        for (int j = 1; (1 << j) <= n; j++) {
            for (int i = 0; i + (1 << (j - 1)) < n; i++) {
                sparse[i][j] = gcd(sparse[i][j - 1], sparse[i + (1 << (j - 1))][j - 1]);
            }
        }
        return sparse;
    }

    private static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    private static class Pair {
        private final int l;
        private final int r;

        public Pair(int l, int r) {
            this.l = l;
            this.r = r;
        }

        public int getL() {
            return l;
        }

        public int getR() {
            return r;
        }

        public int getSpan() {
            return getR() - getL() + 1;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Pair pair = (Pair) o;
            return getL() == pair.getL() && getR() == pair.getR();
        }

        @Override
        public int hashCode() {
            int result = getL();
            result = 31 * result + getR();
            return result;
        }
    }
}