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.*;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class D implements Runnable {

    // leave empty to read from stdin/stdout
    private static final String TASK_NAME_FOR_IO = "";

    // file names
    private static final String FILE_IN = TASK_NAME_FOR_IO + ".in";
    private static final String FILE_OUT = TASK_NAME_FOR_IO + ".out";

    BufferedReader in;
    PrintWriter out;
    StringTokenizer tokenizer = new StringTokenizer("");

    public static void main(String[] args) {
        new Thread(new D()).start();
    }

    int n, answer;
    double[] a;

    private void solve() throws IOException {
        n = nextInt();
        a = new double[n];
        for (int i = 0; i < n; i++) {
            a[i] = nextInt();
        }

        answer = 2;
        if (n == 1) {
            answer = 0;
        } else if (n == 2) {
            if (good(a[0], a[1] / a[0], false, Integer.MAX_VALUE)) {
                answer = 0;
            } else {
                answer = 1;
            }
        } else {
            if (good(a[0], a[1] / a[0], false, Integer.MAX_VALUE)) {
                answer = 0;
            } else if (good(a[0], a[1] / a[0], true, Integer.MAX_VALUE)) { // 0, 1, one skip
                answer = 1;
            } else if (good(a[0], a[2] / a[0], false, 1)) { // 0, [1] skipped, 2, no skips allowed
                answer = 1;
            } else if (good(a[1], a[2] / a[1], false, 0)) { // 0 [skipped], 1, 2, no skips allowed
                answer = 1;
            }
        }

        out.print(answer);
    }

    double EPS = 1e-8;

    private boolean good(double c, double b, boolean skipAllowed, int explicitSkipIdx) {
        if (Double.isNaN(b) || Double.isInfinite(b)) {
            b = 0.0;
        }

        for (int i = 0; i < n; i++) {

            if (i == explicitSkipIdx) {
                continue;
            }

            if (Math.abs(a[i] - c) > EPS) {

                if (skipAllowed) {
                    skipAllowed = false;
                    continue;
                }

                return false;
            }

            c *= b;
        }

        return true;
    }

    public void run() {
        long timeStart = System.currentTimeMillis();
        try {

            if (TASK_NAME_FOR_IO.length() > 0) {
                in = new BufferedReader(new FileReader(FILE_IN));
                out = new PrintWriter(new FileWriter(FILE_OUT));
            } else {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(new OutputStreamWriter(System.out));
            }

            solve();

            in.close();
            out.close();
        } catch (IOException e) {
            throw new IllegalStateException(e);
        }
        long timeEnd = System.currentTimeMillis();
        System.out.println("Time spent: " + (timeEnd - timeStart) + " ms");
    }

    private String nextToken() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            String line = in.readLine();
            if (line == null) {
                return null;
            }
            tokenizer = new StringTokenizer(line);
        }
        return tokenizer.nextToken();
    }

    private int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    private BigInteger nextBigInt() throws IOException {
        return new BigInteger(nextToken());
    }

    private long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    private double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

}