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 cf359d {
  static FastIO in = new FastIO(), out = in;

  public static void main(String[] args) {
    int n = in.nextInt();
    int[] v = new int[n];
    for(int i=0; i<n; i++) v[i] = in.nextInt();

    int lo = 0, hi = n-1;
    while(hi - lo > 2) {
      int mid = (hi+lo)/2;
      if(test(v,mid).size() == 0) hi = mid;
      else lo = mid;
    }
    
    ArrayList<Integer> ans;
    while((ans=test(v,hi)).size() == 0) hi--;
    out.println(ans.size() + " "+hi);
    for(int x : ans) out.print(x+" ");
    out.println();
    out.close();
  }
  static ArrayList<Integer> test(int[] v, int ans) {
    MinDeque min = new MinDeque(ans+1);
    GCDDeque gcd = new GCDDeque(ans+1);
    ArrayList<Integer> ret = new ArrayList<Integer>();
    for(int i=0; i<ans; i++) {
      min.addFirst(v[i]);
      gcd.addFirst(v[i]);
    }
    for(int i=ans; i<v.length; i++) {
      min.addFirst(v[i]);
      gcd.addFirst(v[i]);
      
      if(min.min() == gcd.gcd())
        ret.add(i-ans+1);
      
      min.pollLast();
      gcd.pollLast();
    }
    return ret;
  }
  static class MinDeque {
    MinStack front, back;
    long[] tmp;
    MinDeque(int n) {
      front = new MinStack(n); back = new MinStack(n);
      tmp = new long[n];
    }
    int size() { return front.size() + back.size(); }
    long min() { return Math.min(front.min(), back.min()); }
    void addFirst(long x) { front.push(x); }
    void addLast(long x) { back.push(x); }
    long pollFirst() {
      if (front.size() == 0) balance(1);
      return front.pop();
    }
    long pollLast() {
      if (back.size() == 0) balance(0);
      return back.pop();
    }
    void balance(int bias) {
      int n = size(), nf = (n+bias)/2, cur=0;
      while (front.size() > 0) tmp[cur++] = front.pop();
      cur = n-1;
      while (back.size() > 0) tmp[cur--] = back.pop();
      for (int i=nf-1; i>=0; i--) front.push(tmp[i]);
      for (int i=nf; i<n; i++) back.push(tmp[i]);
    }

    static class MinStack {
      long[] stk, min;
      int ptr;
      MinStack(int n) {
        stk = new long[n+1];
        Arrays.fill(min = new long[n+1], Long.MAX_VALUE);
      }
      int size() { return ptr; }
      void push(long x) { min[++ptr] = Math.min(min[ptr-1],stk[ptr]=x); }
      long pop() { return stk[ptr--]; }
      long min() { return min[ptr]; }
    }
  }
  static class GCDDeque {
    GCDStack front, back;
    long[] tmp;
    GCDDeque(int n) {
      front = new GCDStack(n); back = new GCDStack(n);
      tmp = new long[n];
    }
    int size() { return front.size() + back.size(); }
    long gcd() { return getGCD(front.gcd(), back.gcd()); }
    void addFirst(long x) { front.push(x); }
    void addLast(long x) { back.push(x); }
    long pollFirst() {
      if (front.size() == 0) balance(1);
      return front.pop();
    }
    long pollLast() {
      if (back.size() == 0) balance(0);
      return back.pop();
    }
    void balance(int bias) {
      int n = size(), nf = (n+bias)/2, cur=0;
      while (front.size() > 0) tmp[cur++] = front.pop();
      cur = n-1;
      while (back.size() > 0) tmp[cur--] = back.pop();
      for (int i=nf-1; i>=0; i--) front.push(tmp[i]);
      for (int i=nf; i<n; i++) back.push(tmp[i]);
    }

    static class GCDStack {
      long[] stk, gcd;
      int ptr;
      GCDStack(int n) {
        stk = new long[n+1];
        Arrays.fill(gcd = new long[n+1], 0);
      }
      int size() { return ptr; }
      void push(long x) { gcd[++ptr] = getGCD(gcd[ptr-1],stk[ptr]=x); }
      long pop() { return stk[ptr--]; }
      long gcd() { return gcd[ptr]; }
    }
  }
  static long getGCD(long a, long b) {
    return b==0?a:getGCD(b,a%b);
  }


  static class FastIO extends PrintWriter {
    BufferedReader br;
    StringTokenizer st;

    public FastIO() {
      this(System.in, System.out);
    }

    public FastIO(InputStream in, OutputStream out) {
      super(new BufferedWriter(new OutputStreamWriter(out)));
      br = new BufferedReader(new InputStreamReader(in));
      scanLine();
    }

    public void scanLine() {
      try {
        st = new StringTokenizer(br.readLine().trim());
      } catch (Exception e) {
        throw new RuntimeException(e.getMessage());
      }
    }

    public int numTokens() {
      if (!st.hasMoreTokens()) {
        scanLine();
        return numTokens();
      }
      return st.countTokens();
    }

    public String next() {
      if (!st.hasMoreTokens()) {
        scanLine();
        return next();
      }
      return st.nextToken();
    }

    public double nextDouble() {
      return Double.parseDouble(next());
    }

    public long nextLong() {
      return Long.parseLong(next());
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }
  }
}
