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

public class Solution
{int n;
 int B[];
PrintWriter out;
BufferedReader in;
StringTokenizer ss;


   void dbg(String s){System.out.println(s);};

   String next_token() throws IOException
   {while (!ss.hasMoreTokens())ss=new StringTokenizer(in.readLine());
    return ss.nextToken();}

   Double _double() throws IOException
   {return Double.parseDouble (next_token());}

   int _int() throws IOException
   {return Integer.parseInt (next_token());}

   long _long() throws IOException
   {return Long.parseLong (next_token());}
int f(int a){
    if(a==1)return 0;
    return a;
}
int ff(int a,int t){
      if(a<=t)return a-1;
      return a;
}


int ans(){
   if(n==1)return 0;
   if(n==2){
       if(B[0]!=0||B[1]==0)return 0;
       return 1;

   }
    boolean ok=true;if(B[0]==0&&B[1]!=0)ok=false;
          for(int i=0;i<n-2&&ok;i++)
              if(B[i]*B[i+2]!=B[i+1]*B[i+1])ok=false;
          if(B[n-2]==0&&B[n-1]!=0)ok=false;
       if(ok)return 0;


   ok=true;if(B[1]==0&&B[2]!=0)ok=false;
      for(int i=1;i<n-2&&ok;i++)
          if(B[i]*B[i+2]!=B[i+1]*B[i+1])ok=false;
      if(B[n-2]==0&&B[n-1]!=0)ok=false;
   if(ok)return 1;



    ok=true;if(B[0]==0&&B[2]!=0)ok=false;
          for(int i=1;i<n-2&&ok;i++)
              if(B[f(i)]*B[i+2]!=B[i+1]*B[i+1])ok=false;
    if(B[f(n-2)]==0&&B[n-1]!=0)ok=false;
    if(ok)return 1;
    

    if(B[1]==0){int t=0;for(int i=2;i<n;i++)if(B[i]!=0)t++;
        if(t<=1)return t;
        if(t!=1)return 2;

    }
    
    if(B[0]==0)return 2;


    int t=-1;
    for(int i=0;i<n-2;i++)
           if(B[ff(i,t)]*B[ff(i+2,t)]!=B[ff(i+1,t)]*B[ff(i+1,t)]){
               if(t!=-1)return 2;
               t=i+2;
           }


 return 1;
}

void run()throws IOException
{
in = new BufferedReader(new InputStreamReader(System.in));
out= new PrintWriter(System.out);
//String name = "file";12
//      in = new BufferedReader(new FileReader(name+".in"));
//      out = new PrintWriter(new File(name+".out"));
ss = new StringTokenizer("  ");


n=_int();
int A[]=new int[n];
B=new int[n];
/*    for(int i=0;i<n;i++){
      int x=_int();
      A[i]=2*Math.abs(x);
        if(x<0)A[i]++;
    }
Arrays.sort(A);
     for(int i=0;i<n;i++){
         B[i]=A[i]/2;
         if(A[i]%2==1)B[i]=-B[i];
     }*/
    for(int i=0;i<n;i++){B[i]=_int();}

    out.println(ans());

out.close();
}

public static void main(String[] args)throws Exception
{
try{new Solution().run();}catch (Exception e){int a[]=new int[2];a[1+3]=2;};
}
}
