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.*;
import static java.lang.Math.*;
import static java.util.Arrays.fill;
import static java.util.Arrays.binarySearch;
import static java.util.Arrays.sort;

public class Main {
	double EPS = 1e-12;

	public static void main(String[] args) throws IOException {
		new Thread(null, new Runnable() {
			public void run() {
				try {
					try {
						if (new File("input.txt").exists())
							System.setIn(new FileInputStream("input.txt"));
					} catch (SecurityException e) {}
					new Main().run();
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
		}, "1", 1L << 24).start(); 
	}

	BufferedReader in;
	PrintWriter out;
	StringTokenizer st = new StringTokenizer("");
	
	int N;
	double[] a;
	
	void run() throws IOException {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		
		N = nextInt();
		a = new double [N];
		
		for (int i = 0; i < N; i++)
			a[i] = nextDouble();
		
		if (N == 1) {
			out.println(0);
			out.close();
			return;
		}
		
		int zc = zeroCount();
		
		if (zc == N) {
			out.println(0);
			out.close();
			return;
		}
		
		if (zc > 1) {
			if (zc == N - 1) {
				out.println(isZero(a[0]) ? 1 : 0);
			} else {
				if (zc == N - 2 && !isZero(a[0]))
					out.println(1);
				else 
					out.println(2);
			}
			out.close();
			return;
		}
		
		if (zc == 1) {
			if (N == 2) {
				out.println(isZero(a[0]) ? 1 : 0);
			} else if (N == 3 || checkWithout(findZero())) {
				out.println(1);
			} else {
				out.println(2);
			}
			out.close();
			return;
		}
		
		if (N < 3) {
			out.println(0);
			out.close();
			return;
		}
		
		if (checkWithout(-2)) {
			out.println(0);
			out.close();
			return;
		}
		
//		if (checkWithout(0) || checkWithout(N - 1)) {
//			out.println(1);
//			out.close();
//			return;
//		}
		
		for (int i = 1; i < N - 1; i++) {
			int prv = i - 1;
			int cur = i;
			int nxt = i + 1;
			
			if (!equals(a[cur] / a[prv], a[nxt] / a[cur])) {
				if (checkWithout(prv) || checkWithout(cur) || checkWithout(nxt))
					out.println(1);
				else
					out.println(2);
				out.close();
				return;
			}
		}
		
		
		out.println(2);
		out.close();
	}
	
	boolean checkWithout(int bad) {
		double b;
		if (bad == 1) {
			if (N < 4 || isZero(a[2]))
				return false;
			b = a[3] / a[2];
		} else {
			if (bad == 0) {
				if (N < 3 || isZero(a[1]))
					return false;
				b = a[2] / a[1];
			} else {
				if (isZero(a[0]))
					return false;
				b = a[1] / a[0];
			}
		}
		for (int i = 1; i < N; i++) {
			int prv = i - 1;
			int cur = i;
			if (prv == bad) {
				prv--;
				if (prv < 0)
					continue;
			}
			if (cur == bad) {
				cur++;
				if (cur >= N)
					continue;
			}
			if (isZero(a[prv]))
				return false;
			double rel = a[cur] / a[prv];
			if (!equals(b, rel))
				return false;
		}
		return true;
	}

	int findZero() {
		for (int i = 0; i < N; i++)
			if (isZero(a[i]))
				return i;
		return -1;
	}

	int zeroCount() {
		int ret = 0;
		for (int i = 0; i < N; i++)
			if (isZero(a[i]))
				ret++;
		return ret;
	}
	
	boolean equals(double x, double y) {
		return isZero(x - y);
	}
	
	boolean isZero(double x) {
		return abs(x) < EPS;
	}

	String nextToken() throws IOException {
		while (!st.hasMoreTokens()) {
			st = new StringTokenizer(in.readLine());
		}
		
		return st.nextToken();
	}
	
	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}
	
	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}
	
	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}
	
	String nextLine() throws IOException {
		st = new StringTokenizer("");
		return in.readLine();
	}
	
	boolean EOF() throws IOException {
		while (!st.hasMoreTokens()) {
			String s = in.readLine();
			
			if (s == null) {
				return true;
			}
			
			st = new StringTokenizer(s);
		}
		
		return false;
	}
}
