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

public class geoprogress {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int size = sc.nextInt();
		double[] arr = new double[size];
		for (int w = 0; w < size; w++) {
			arr[w] = sc.nextInt();
		}
		int ans1 = 0;
		int ans2 = 1;
		int ans3=1;
		if (size == 1)
			System.out.println(0);
		else if(size==2)
		{
			if(arr[0]==0 && arr[1]==0)
				System.out.println("0");
			else if(arr[0]==0 && arr[1]!=0)
				System.out.println("1");
			else System.out.println("0");
		}
		else {
			double b = arr[1] / arr[0];
			if (arr[0] == 0)
			{
				int nzero=0;
				for(int x=0;x<arr.length;x++)
					if(arr[x]!=0)nzero++;
				ans1=nzero;
			}
			else
			for (int x = 2; x < size; x++) {
				// System.out.println(x+" "+ans1);
				if (arr[x - 1] * b != arr[x]) {
					ans1++;
					if (x + 1 < size && arr[x - 1] * b == arr[x + 1]) {
						x++;
					} else if (x + 1 == size)
						continue;
					else {
						ans1 = 2;
					}
					if (ans1 == 2)
						break;
				}
			}
			if (size > 2) {
				b = arr[2] / arr[1];
				if (arr[1] == 0)
				{
					int nzero=1;
					for(int x=1;x<arr.length;x++)
						if(arr[x]!=0)nzero++;
					ans2=nzero;
				}
				else
				for (int x = 3; x < size; x++) {
					if (arr[x - 1] * b != arr[x]) {
						ans2++;
						if (x + 1 < size && arr[x - 1] * b == arr[x + 1]) {
							x++;
						} else if (x + 1 == size)
							continue;
						else {
							ans2 = 2;
						}
						if (ans2 == 2)
							break;

					}
				}
			}
			if (size > 2) {
				b = arr[2] / arr[0];
				if (arr[0] == 0)
				{
					int nzero=0;
					for(int x=0;x<arr.length;x++)
						if(arr[x]!=0)nzero++;
					ans3=nzero;
				}
				else
				for (int x = 3; x < size; x++) {
					if (arr[x - 1] * b != arr[x]) {
						ans3++;
						if (x + 1 < size && arr[x - 1] * b == arr[x + 1]) {
							x++;
						} else if (x + 1 == size)
							continue;
						else {
							ans3 = 2;
						}
						if (ans3 == 2)
							break;

					}
				}
			}
			//System.out.println(ans1+" "+ans2+" "+ans3);
			System.out.println(Math.min(Math.min(2,ans1), Math.min(ans2,ans3)));
		}

	}
}
