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
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.TreeSet;
import java.util.StringTokenizer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Zyflair Griffane
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		PandaScanner in = new PandaScanner(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		D solver = new D();
		solver.solve(1, in, out);
		out.close();
	}
}

class D {
    final int UNDEFINED = 1000000;
    public void solve(int testNumber, PandaScanner in, PrintWriter out) {
        int n = in.nextInt();
        int[] seq = new int[n];
        for (int i = 0; i < n; i++) {
            seq[i] = in.nextInt();
        }
        int res = Math.min(allZero(seq), allSame(seq));
        res = Math.min(res, alternating(seq));
        if (isSequence(seq, -1)) {
            res = 0;
        }
        if (isSequence(seq, 0)) {
            res = Math.min(res, 1);
        }
        if (seq.length < 30) {
            for (int i = 0; i < seq.length; i++) {
                if (isSequence(seq, i)) {
                    res = Math.min(res, 1);
                    break;
                }
            }
        }
        out.println(Math.min(res, 2));
    }
    boolean isSequence(int[] seq, int skip) {
        int a = UNDEFINED;
        int b = UNDEFINED;
        for (int i = 0; i < seq.length; i++) {
            if (i == skip) {
                continue;
            }
            if (a != UNDEFINED && b != UNDEFINED) {
                if (a * seq[i] != b * b) {
                    return false;
                }
            }
            a = b;
            b = seq[i];
            if (b == 0) {
                return false;
            }
        }
        return true;
    }
    int allZero(int[] seq) {
        int cost = 0;
        for (int i = 1; i < seq.length; i++) {
            if (seq[i] != 0) {
                cost++;
            }
        }
        return cost;
    }
    int allSame(int[] seq) {
        int[] compressedSeq = ArrayUtil.compress(seq);
        Arrays.sort(compressedSeq);
        int length = compressedSeq.length;
        if (compressedSeq[length - 1] > 1 || compressedSeq[length - 1] == 0 || length < 4) {
            return compressedSeq[length - 1];
        }
        if (compressedSeq[1] == 0 && compressedSeq[length - 2] == 1) {
            return 2;
        }
        return 1;
    }
    int alternating(int[] seq) {
        int cost = 0;
        int curr = seq[0];
        for (int i = 1; i < seq.length; i++) {
            if (-curr != seq[i]) {
                cost++;
            }
            else {
                curr = -curr;
            }
        }
        return cost;
    }
}

class PandaScanner {
    public BufferedReader br;
    public StringTokenizer st;
    public InputStream in;

    public PandaScanner(InputStream in) {
        br = new BufferedReader(new InputStreamReader(this.in = in));
    }

    public String nextLine() {
        try {
            return br.readLine();
        }
        catch (Exception e) {
            return null;
        }
    }

    public String next() {
        if (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(nextLine().trim());
            return next();
        }
        return st.nextToken();
    }

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

    }

class ArrayUtil {

    /**
     * Returns a compressed integer array that holds elements from 0 to n, where n is the number of distinct elements in the original array.
     * @param arr The array to compress
     * @return The compressed array
     */
    public static int[] compress(int[] arr) {
        TreeSet<Integer> set = new TreeSet<Integer>();
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i: arr) {
            set.add(i);
        }
        int cnt = 0;
        for (Integer i: set) {
            map.put(i, cnt);
            cnt++;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = map.get(arr[i]);
        }
        return res;
    }

    }

