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

public class Z implements Runnable{

    BufferedReader in;
    StringTokenizer st;
    PrintWriter out;
    
    void solve() throws IOException{
        int n = nextInt();
        int[] a = new int[n];
        if(n == 1) {
            out.print("0");
            return;
        }
        for(int i = 0; i < n; i++)
            a[i] = nextInt();
        if(n == 2) {
            if(a[0] == 0 && a[1] != 0)
                out.print("1");
            else
                out.print("0");
            return;
        }
        
        int flag = 0, b = 0, c;
        
        for(int i = 1; i < n; i++)
            if(a[i] == 0)
                flag++;
        if(flag == n - 1) {
            out.print("0");
            return;
        }
        if(flag == n - 2) {
            out.print("1");
            return;
        }
        flag = 0;
        for(int i = 1; i < n; i++)
            if(a[i] != a[0])
                flag++;
        if(flag == 0) {
            out.print("0");
            return;
        }
        if(flag == 1) {
            out.print("1");
            return;
        }
        flag = 0;
        if(a[0] != a[1])
            flag++;
        for(int i = 2; i < n; i++)
            if(a[i] != a[1])
                flag++;
        if(flag == 1) {
            out.print("1");
            return;
        }
        
        int[] wz = new int[n];
        int nn = 0;
        double tmp;
        for(int i = 0; i < n; i++)
            if(a[i] != 0) {
                wz[nn++] = a[i];
            }
        if(n - nn > 1) {
            out.print("2");
            return;
        }
        if(n - nn == 1) {
            tmp = wz[1] / (double)wz[0];
            flag = 0;
            for(int i = 2; i < nn; i++)
                if(Math.abs(wz[i] / (double)wz[i - 1] - tmp) > 1e-5)
                    flag++;
            if(flag == 0) {
                out.print("1");
                return;
            }
            else {
                out.print("2");
                return;
            }
        }
    
        c = a[0];
        tmp = a[1] / (double)c;
        flag = 0;
        for(int i = 2; i < n; i++)
            if(Math.abs(a[i] / (double)a[i - 1] - tmp) > 1e-5) {
                flag++;
                if(Math.abs(a[i - 1] / (double)a[i - 2] - tmp) > 1e-5 && Math.abs(a[i] / (double)a[i - 2] - tmp) < 1e-5)
                    flag--;
            }
        if(flag == 0) {
            out.print("0");
            return;
        }
        if(flag == 1) {
            out.print("1");
            return;
        }
        c = a[1];
        tmp = a[2] / (double)c;
        flag = 0;
        for(int i = 3; i < n; i++)
            if(Math.abs(a[i] / (double)a[i - 1] - tmp) > 1e-5)
                flag++;
        if(flag == 0) {
            out.print("1");
            return;
        }
        c = a[0];
        tmp = a[2] / (double)c;
        flag = 0;
        for(int i = 3; i < n; i++)
            if(Math.abs(a[i] / (double)a[i - 1] - tmp) > 1e-5)
                flag++;
        if(flag == 0) {
            out.print("1");
        }
        else
            out.print("2");
    }
    
    public void run() {
        try {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
            eat("");
            solve();
            out.close();
            in.close();
        } catch (IOException ex) {
            throw new RuntimeException(ex);
        }
    }
    
    void eat(String s) {
        st = new StringTokenizer(s);
    }
    
    String next() throws IOException {
        while (!st.hasMoreTokens()) {
            String line = in.readLine();
            if (line == null) {
                return null;
            }
            eat(line);
        }
        return st.nextToken();
    }
    
    int nextInt() throws IOException {
        return Integer.parseInt(next());
    }
    
    long nextLong() throws IOException {
        return Long.parseLong(next());
    }
    
    double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
    
    public static void main(String[] args) {
        Locale.setDefault(Locale.US);
        new Thread(new Z()).start();
    }

}
