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>
using namespace std;
int main() {
  long long n;
  cin >> n;
  vector<long long> vec(n);
  for (long long i = 0; i < ((long long)n); i++) cin >> vec[i];
  if (n == 1) {
    cout << 0 << endl;
    return 0;
  };
  if (count(vec.begin(), vec.end(), 0) == n - 1 + ((vec[0] == 0) ? 1 : 0)) {
    cout << 0 << endl;
    return 0;
  };
  if (count(vec.begin(), vec.end(), 0) == 0) {
    long long dif0 = vec[1] / vec[0], dif1 = vec[0] / vec[1];
    bool ok0 = true, ok1 = true;
    for (long long i = 0; i < ((long long)n - 1); i++)
      if (vec[i] * dif0 != vec[i + 1]) ok0 = false;
    for (long long i = 0; i < ((long long)n - 1); i++)
      if (vec[i + 1] * dif1 != vec[i]) ok1 = false;
    if (ok0 || ok1) {
      cout << 0 << endl;
      return 0;
    };
  }
  long long top = 0, last = n - 1;
  while (vec[top] == vec[top + 1]) top++;
  while (vec[last] == vec[last - 1]) last--;
  if (last == 1 || top == n - 2 ||
      (last <= top + 2 && vec[last - 2] == vec[last])) {
    cout << 1 << endl;
    return 0;
  };
  top = 0, last = n - 1;
  while (vec[top] == -vec[top + 1]) top++;
  while (vec[last] == -vec[last - 1]) last--;
  if (last == 1 || top == n - 2 ||
      (last <= top + 2 && vec[last - 2] == -vec[last])) {
    cout << 1 << endl;
    return 0;
  };
  if (10005 < n) {
    cout << 2 << endl;
    return 0;
  };
  for (long long i = 0; i < ((long long)n); i++) {
    bool ok0 = true;
    for (long long j = 1; j < n; j++)
      if (j != i && vec[j] != 0) ok0 = false;
    if (ok0) {
      cout << 1 << endl;
      return 0;
    };
    if (count(vec.begin(), vec.end(), 0) <= ((vec[i] == 0) ? 1 : 0)) {
      long long dif0 = vec[1 + (i <= 1)] / vec[0 + (i <= 0)],
                dif1 = vec[0 + (i <= 0)] / vec[1 + (i <= 1)];
      bool ok0 = true, ok1 = true;
      for (long long j = 0; j < ((long long)n - 2); j++)
        if (vec[j + (i <= j)] * dif0 != vec[j + 1 + (i <= j + 1)]) ok0 = false;
      for (long long j = 0; j < ((long long)n - 2); j++)
        if (vec[j + 1 + (i <= j + 1)] * dif1 != vec[j + (i <= j)]) ok1 = false;
      if (ok0 || ok1) {
        cout << 1 << endl;
        return 0;
      };
    }
  }
  {
    cout << 2 << endl;
    return 0;
  };
}
