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 static java.lang.Math.*;
public class D {
	public static void main(String[] args) throws Exception{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.valueOf(in.readLine().trim());
		int[] V = new int[N];
		StringTokenizer stok = new StringTokenizer(in.readLine());
		for(int i = 0; i < N;i++)
			V[i] = Integer.valueOf(stok.nextToken());
		if(check(V)){
			System.out.println("0");
			System.exit(0);
		}
		if(N > 100){
			HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>();
			for(int v:V){
				if(!freq.containsKey(v))
					freq.put(v, 0);
				freq.put(v, freq.get(v)+1);
			}
			if(freq.size() > 3){
				System.out.println("2");
				System.exit(0);
			}
			for(int i = 0; i < N;i++){
				if(freq.get(V[i]) <= 3){
					test(i, V, N);
				}
			}
			if(freq.size() == 2){
				int bad = 0;
				for(int i = 0; i < N-1;i++){
					if(V[i] != -V[i+1]){
						bad++;
					}
				}
				if(bad == 1){
					System.out.println("1");
					System.exit(0);
				}
			}
		}else{
			for(int i = 0; i < N;i++){
				test(i, V, N);
			}
		}
		System.out.println("2");
	}		
	private static void test(int i, int[] V, int N) {
		int[] T = new int[N-1];
		for(int j = 0; j < i;j++)
			T[j] = V[j];
		for(int j = i+1; j < N;j++)
			T[j-1] = V[j];
		if(check(T)){
			System.out.println("1");
			System.exit(0);
		}
	}
	static boolean check(int[] V){
		if(V.length <= 1)
			return true;
		double a = V[0];
		double b;
		if(a == 0)
			b = 0;
		else
			b = V[1]/(double)a;
		double at = a;
		for(int v:V){
			if(abs(at-v) > 1e-9)
				return false;
			at *= b;
		}
		return true;
	}
}