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

public class D{

    int[]ar;
    int oo = 2000000000;
    void read(){
    
        Scanner s = new Scanner(System.in);
        int n  = s.nextInt();
        int i = 0;
        ar = new int[n];
        while(i<n){
            ar[i++] = s.nextInt();
        }
        if(n == 1 || isGeometric(0,n-1,ar)){
            System.out.println(0);
        }
        else if( recurse(0,n-1)) {
            System.out.println(1);
        }
        else{
             System.out.println(2);
        }

        
    }
    
    boolean isGeometric(int from,int to,int[]ar){
        if(to - from + 1 == 1) return true;
        if(ar[from] == 0){
              boolean f = true;
             for(int i = from+1;i<=to;++i) {
                 if(ar[i] != 0){
                       f = false;
                       return false;
                  }
              }
              if(f)
             return true;
         }
        double eps = 1e-9;
        double b = 0;
        if(ar[from] == 0&&ar[from+1] == 0) b = 0;
        else if(ar[from] == 0) b = oo;
        else  b = (double)ar[from + 1]/ar[from];
        for(int i = from+2;i<=to;++i){
        
            double d = 0;
            if(ar[i-1] == 0&&ar[i] == 0) d = 0;
            else if(ar[i-1] == 0) b = oo;
            else  d = (double)ar[i]/ar[i-1];
            if(Math.abs(d - b )>eps) return false;
        }
        return true;
        
    }
        
    
    boolean bruteForce(int from,int to){
    
        int[]inter = new int[to - from ];
        int sz = 0;
        for(int i = from;i<=to;++i){
            sz = 0;
            for(int j = from;j<=to;++j){
                if(i == j) continue;
                inter[sz++] = ar[j];
            }
            if(isGeometric(0,inter.length-1,inter)) return true;
        }
        return false;
    }
    boolean recurse(int from,int to){
    
        if(to - from + 1<7) return bruteForce(from,to);
        int mid = (from + to)/2;
        boolean f1 = isGeometric(from,mid,ar);
        boolean f2 = isGeometric(mid+1,to,ar);
        if(!f1&&!f2) return false;
        if(!f1) return recurse(from,mid);
        else return recurse(mid+1,to);
        
    }

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

}