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;
long mn[maxn][3];
long mas[maxn];
long n, q, cht, g, first;
bool nuls;
bool nowres;
long gcd(long a, long b) {
  if ((a == 0) || (b == 0))
    return (a + b);
  else if (a > b)
    return (gcd(a % b, b));
  else
    return (gcd(a, b % a));
}
void solve_nuls() {
  nowres = true;
  long h;
  long pp = 0;
  for (long q = 1; q <= n; q++)
    if (mas[q] != 0) pp++;
  if (mas[1] == 0) {
    if (pp == 0)
      printf("0");
    else if (pp == 1) {
      if (mas[1] != 0)
        printf("0");
      else
        printf("1");
    } else {
      if (n - pp == 1) {
        nowres = false;
        for (h = 1; h <= n; h++)
          if (mas[h] == 0) break;
        for (long j = h; j <= n - 1; j++) mas[j] = mas[j + 1];
        n--;
      } else
        printf("2");
    }
  } else if (pp == 1)
    printf("0");
  else if (pp == 2)
    printf("1");
  else if (n - pp == 1) {
    nowres = false;
    long h, g;
    for (h = 1; h <= n; h++)
      if (mas[h] == 0) break;
    for (g = h; g <= n - 1; g++) mas[g] = mas[g + 1];
    n--;
  } else
    printf("2");
}
long abss(long x) {
  if (x < 0)
    return (-x);
  else
    return (x);
}
int main() {
  scanf("%ld", &n);
  nuls = false;
  for (q = 1; q <= n; q++) {
    scanf("%ld", &mas[q]);
    if (mas[q] == 0) nuls = true;
  }
  nowres = true;
  if (nuls == true) {
    solve_nuls();
    if (nowres == true) return 0;
  }
  for (q = 1; q <= n - 1; q++) {
    g = gcd(abss(mas[q + 1]), abss(mas[q]));
    mn[q][1] = mas[q + 1] / g;
    mn[q][2] = mas[q] / g;
  }
  cht = 0;
  first = -1;
  bool fail = false;
  for (q = 2; q <= n - 1; q++)
    if (mn[q][1] * mn[q - 1][2] != mn[q][2] * mn[q - 1][1]) {
      if (first == -1) first = q;
      if (q - first > 2) fail = true;
      cht++;
    }
  if (fail == true) {
    printf("2");
    return 0;
  }
  if (nowres == false) {
    if (cht == 0)
      printf("1");
    else
      printf("2");
    return 0;
  }
  if (cht == 0)
    printf("0");
  else {
    if (first == n - 1)
      printf("1");
    else if (first == 2) {
      g = gcd(abss(mas[first + 2]), abss(mas[first]));
      mn[first + 1][1] = mas[first + 2] / g;
      mn[first + 1][2] = mas[first] / g;
      if (mn[first - 1][1] * mn[first + 1][2] !=
          mn[first - 1][2] * mn[first + 1][1]) {
        if (cht == 1)
          printf("1");
        else
          printf("2");
      } else
        printf("1");
    } else {
      g = gcd(abss(mas[first + 2]), abss(mas[first]));
      mn[first + 1][1] = mas[first + 2] / g;
      mn[first + 1][2] = mas[first] / g;
      if (mn[first - 1][1] * mn[first + 1][2] !=
          mn[first - 1][2] * mn[first + 1][1])
        printf("2");
      else
        printf("1");
    }
  }
}
