Polycarp loves geometric progressions — he collects them. However, as such progressions occur very rarely, he also loves the sequences of numbers where it is enough to delete a single element to get a geometric progression.

In this task we shall define geometric progressions as finite sequences of numbers a1, a2, ..., ak, where ai = c·bi - 1 for some real numbers c and b. For example, the sequences [2, -4, 8], [0, 0, 0, 0], [199] are geometric progressions and [0, 1, 2, 3] is not.

Recently Polycarp has found a sequence and he can't classify it. Help him to do it. Determine whether it is a geometric progression. If it is not, check if it can become a geometric progression if an element is deleted from it.

Input

The first line contains an integer n (1 ≤ n ≤ 105) — the number of elements in the given sequence. The second line contains the given sequence. The numbers are space-separated. All the elements of the given sequence are integers and their absolute value does not exceed 104.

Output

Print 0, if the given sequence is a geometric progression. Otherwise, check if it is possible to make the sequence a geometric progression by deleting a single element. If it is possible, print 1. If it is impossible, print 2.

Examples

Input

4
3 6 12 24


Output

0


Input

4
-8 -16 24 -32


Output

1


Input

4
0 1 2 3


Output

2
#include <bits/stdc++.h>
const long maxn = 100001;
const double eps = 1.0e-12;
long a[maxn];
long n, q;
double b;
bool exb;
long temp, h, choice, left, right;
bool possible;
double abss(double x) {
  if (x < eps)
    return (-x);
  else
    return (x);
}
bool equal(long a0, long a1) {
  if (a0 == 0)
    return (a1 == 0);
  else if (exb == false)
    return (true);
  else
    return (abss(a1 - b * a0) < eps);
}
bool check(long start, long finish) {
  exb = false;
  bool confl = false;
  for (long i = start + 1; i <= finish; i++) {
    bool now = equal(a[i - 1], a[i]);
    if (now == false) {
      confl = true;
      break;
    } else if (a[i - 1] != 0) {
      exb = true;
      double b1 = a[i];
      double b2 = a[i - 1];
      b = b1 / b2;
    }
  }
  return (!confl);
}
void precalc() {
  bool now;
  long start, finish;
  start = 1;
  finish = n;
  while (start < finish) {
    long middle = (start + finish) / 2 + 1;
    now = check(1, middle);
    if (now == false)
      finish = middle - 1;
    else
      start = middle;
  }
  right = start;
  start = 1;
  finish = n;
  while (start < finish) {
    long middle = (start + finish) / 2;
    now = check(middle, n);
    if (now == false)
      start = middle + 1;
    else
      finish = middle;
  }
  left = start;
}
long max(long a, long b) {
  if (a > b)
    return (a);
  else
    return (b);
}
long min(long a, long b) {
  if (a < b)
    return (a);
  else
    return (b);
}
int main() {
  scanf("%ld", &n);
  for (q = 1; q <= n; q++) scanf("%ld", &a[q]);
  precalc();
  if (check(1, n) == true)
    printf("0");
  else {
    possible = false;
    for (choice = 1; choice <= n; choice++)
      if ((right >= choice - 1) && (left <= choice + 1)) {
        temp = a[choice];
        for (h = choice; h <= n - 1; h++) a[h] = a[h + 1];
        if (check(1, n - 1) == true) {
          possible = true;
          break;
        }
        for (h = n; h >= choice + 1; h--) a[h] = a[h - 1];
        a[choice] = temp;
      }
    if (possible == false)
      printf("2");
    else
      printf("1");
  }
}
