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.lang.*;
import java.io.*;
import java.util.*;
import java.math.*;

public class D implements Runnable{
    private static BufferedReader br = null;
    private static PrintWriter out = null;
    private static StringTokenizer stk = null;
    
    public static void main(String[] args) {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        (new Thread(new D())).start();
    }
    
    private void loadLine() {
        try {
            stk = new StringTokenizer(br.readLine());
        }
        catch (IOException e) {
            e.printStackTrace();
        }
    }
    
    private String nextLine() {
        try {
            return br.readLine();
        }
        catch (IOException e) {
            e.printStackTrace();
        }
        return null;
    }
    
    private Integer nextInt() {
        while (stk==null||!stk.hasMoreTokens()) loadLine();
        return Integer.parseInt(stk.nextToken());
    }
    
    private Long nextLong() {
        while (stk==null||!stk.hasMoreTokens()) loadLine();
        return Long.parseLong(stk.nextToken());
    }
    
    private String nextWord() {
        while (stk==null||!stk.hasMoreTokens()) loadLine();
        return (stk.nextToken());
    }
    
    private Double nextDouble() {
        while (stk==null||!stk.hasMoreTokens()) loadLine();
        return Double.parseDouble(stk.nextToken());
    }
    
    
    public void run() {
        int n = nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = nextInt();
        }
        if (n == 1 || n == 2) {
            if (n==1 || (arr[0] != 0 || (arr[0] == arr[1])))
                out.println(0);
            else if (arr[0] == 0 && arr[1] != 0) {
                out.println(1);
            }
        }
        else {
            //equal
            HashMap<Integer, Integer> h = new HashMap<Integer, Integer>();
            for (int i = 0; i < n; ++i) {
                if (!h.containsKey(arr[i])) {
                    h.put(arr[i], 0);
                }
                int tmp = h.get(arr[i]);
                h.put(arr[i], tmp+1);
            }
            boolean one = false;
            boolean zero = false;
            for (int k : h.keySet()) {
                if (h.get(k) == 1) {
                    one = true;
                }
                else {
                    if (k == 0) {
                        zero = true;
                    }
                }
            }
            if (h.size() == 1) {
                out.println(0);
            }
            else if (h.size() == 2 && one && !zero) {
                out.println(1);
            }
            else {
                double d1 = 1;
                double d2 = 1;
                double d3 = 1;
                if (arr[0] != 0) {
                    d1 = 1.0*arr[1]/arr[0];
                    d2 = 1.0*arr[2]/arr[0];
                }
                if (arr[1] != 0) {
                    d3 = 1.0*arr[2]/arr[1];
                }
                
                int e1 = 0;
                int e2 = 0;
                int e3 = 0;
                ArrayList<Integer> p1 = new ArrayList<Integer>();
                ArrayList<Integer> p2 = new ArrayList<Integer>();
                ArrayList<Integer> p3 = new ArrayList<Integer>();
                for (int i = 1; i < n; ++i) {
                    if (arr[i-1]*d1 != arr[i]) {
                        ++e1;
                        p1.add(i);
                    }
                    if (arr[i-1]*d2 != arr[i]) {
                        ++e2;
                        p2.add(i);
                    }
                    if (arr[i-1]*d3 != arr[i]) {
                        ++e3;
                        p3.add(i);
                    }
                }
                
                if (e1 == 0) {
                    out.println(0);
                }
                else if (e1 > 2 && e2 > 2 && e3 > 2) {
                    out.println(2);
                }
                else {
                    boolean got = false;
                    if (e1 <= 2) {
                        if (e1 == 1 || (p1.get(1) - 1 == p1.get(0) && arr[p1.get(0)-1]*d1 == arr[p1.get(1)])) {
                            got = true;
                        }
                    }
                    if (e2 <= 2) {
                        if (e2 == 1 || (p2.get(1) - 1 == p2.get(0) && arr[p2.get(0)-1]*d2 == arr[p2.get(1)])) {
                            got = true;
                        }
                    }
                    if (e3 <= 2) {
                        if (e3 == 1 || (p3.get(1) - 1 == p3.get(0) && arr[p3.get(0)-1]*d3 == arr[p3.get(1)])) {
                            got = true;
                        }
                    }
                    
                    if (!got) {
                        out.println(2);
                    }
                    else {
                        out.println(1);
                    }
                }
            }
        }
        out.flush();
    }
}

