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
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */


import java.util.* ;
import java.io.* ;
import java.math.* ;
/************************
 *                      *
 *    Lord Klotski      *
 *                      *
 ***********************/
public class D
{
    static int I ;
    public static boolean attempt(int X, double[] nums)
    {
        double[] tmp = new double[nums.length] ; for (int i = 0 ;i < nums.length ; i ++) tmp[i] = nums[i] ;
        tmp[X] = 999999 ; Arrays.sort(tmp) ;
        double[] difs = new double[nums.length-2] ;
        for (int i = 0 ; i < nums.length-2 ; i ++)
        {
            difs[i] = tmp[i+1]/tmp[i] ;
        }
        double eps = Math.pow(10,-8) ;
        boolean fail = false ;
        for (int i = 0 ; i < nums.length-3 ; i ++)
        {
            if (Math.abs(difs[i]-difs[i+1]) > eps ) fail = true ;
        }
        return !fail ;
    }

    public static boolean attempt2(int X, int[] nums)
    {
        int[] tmp = new int[nums.length] ; for (int i = 0 ;i < nums.length ; i ++) tmp[i] = nums[i] ;
        int L = tmp.length ;
        if (X >= 0 && X < L)
        {
            tmp[X] = 9999999 ; lolsort(tmp,X) ; L -- ;
           // System.out.println(tmp[0] + " " + tmp[1] + " " + tmp[2]);
        }
        double eps = Math.pow(10,-8) ;
        if (L == 1) return true ;
        double r = findR(tmp[0],tmp[1]) ; if (r == 999999) return false ;
        for (int i = 1 ; i < L-1 ; i ++)
        {
            if (Math.abs(findR(tmp[i],tmp[i+1]) - r) > eps){if (I == -1) I = i ; return false ;}
        }
        return true ;

    }
    public static void lolsort(int[] x, int i)
    {
        for (int j = i; j < x.length-1 ; j ++) x[j] = x[j+1] ;

        x[x.length-1] = 9999999 ;
    }

    public static double findR(int A, int B)
    {
        // r*A = B
        if (A == 0 && B == 0) return 0 ;
        if (A == 0 && B != 0) return 999999 ;
        return (B+0.0)/A ;
    }

    public static void main(String[] args)
    {
        /*Scanner input = new Scanner(System.in) ;
        int T = input.nextInt() ;
        double[] nums = new double[T] ; double eps = Math.pow(10,-8) ;
        for (int i = 0 ; i < T ; i ++) nums[i] = input.nextDouble() ;

        if (nums[0] == nums[1] == 0)
        {

        }

        if (T == 1 || T == 2) System.out.println("0");
        else
        {
            double[] difs = new double[T-1] ;
            for (int i = 0 ; i < T-1 ; i ++)
            {
                difs[i] = nums[i+1]/nums[i] ;
            }
            boolean fail = false ;
            for (int i = 0 ; i < T-2 ; i ++)
            {
                if (Math.abs(difs[i]-difs[i+1]) > eps ) fail = true ;
            }
            if (!fail) System.out.println("0");
            else
            {
                int ans = 0 ;
                for (int i = 0; i < T-2 ; i ++)
                {
                    if (difs[i+1] != difs[i]) {ans = i ; break ;}
                }

                // spam some numbers lol
                boolean win = false ;
                win |= attempt(Math.max(0,ans),nums) ;
                win |= attempt(ans+1,nums) ;
                win |= attempt(ans+2,nums) ;

                if (win) System.out.println("1");
                else System.out.println("2");
            }
        }
    }*/
        Scanner input = new Scanner(System.in) ;
        int T = input.nextInt() ;
        int[] nums = new int[T] ;
        for (int i = 0 ; i < T ; i ++) nums[i] = input.nextInt() ;
        I = -1 ;
        if (T == 1) System.out.println("0");
        else
        {
            if (attempt2(-1,nums)) System.out.println("0");
            else
            {
                boolean win = attempt2(I,nums) ;
                win |= attempt2(I+1,nums) ;
                win |= attempt2(I+2,nums) ;
                win |= attempt2(I-1,nums) ;
                //System.out.println(I);
                //System.out.println(attempt2(I+1,nums));
                if (win)
                    System.out.println("1");
                else
                    System.out.println("2");

            }



        }


    }
}
