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

public class Main implements Runnable {
	BufferedReader in;
	PrintStream out;  
	StringTokenizer st = new StringTokenizer("");
	static boolean local = false;

	int n;
	
	public static void main(String [] args) throws Exception {
		if (args.length > 0) local = true;
		new Thread(new Main()).start();
	}

	void printExit(String s) {
		out.println(s);
		System.exit(0);
	}

	boolean allZero(int [] a, int l, int r) {
		for (int i = l; i <= r; i++)
			if (a[i] != 0)
				return false;
		return true;
	}

	boolean good(int [] a, int l, int r) {
		if (l == r) return true;
		int c = a[l];
		if (c == 0) {
			return allZero(a, l, r);
		}
		if (a[l + 1] % c != 0) return false;
		int d = a[l + 1] / c;
		long cur = c * d;
		for (int i = l + 1; i <= r; i++) {
			if (a[i] != cur) {
				return false;
			}
			cur *= d;
		}
		return true;
	}

	boolean go(int [] a) {
		int c = a[0];
		if (c == 0) {
			throw new AssertionError();
		}
		int d = a[1] / c;
		long cur = c * d;
		int skip = 0;
		for (int i = 1; i < n; i++) {
			if (a[i] != cur) {
				skip++;
			} else {
				cur = cur * d;
			}	
		}
		if (skip == 0) throw new AssertionError();
		return skip <= 1;
	}

	int get(int [] a) {
		for (int i = 0; i < a.length; i++) if (a[i] == 0) throw new AssertionError();
		if (a.length == 1 || good(a, 0, n - 1)) return 0;
		if (good(a, 1, n - 1)) return 1;
		//start with c
		int [] arr = new int[n - 1];
		arr[0] = a[0];
		for (int i = 2; i < n; i++) {
			arr[i - 1] = a[i];
		}
		if (good(arr, 0, n - 2)) return 1;
		//start with c, bc
		if (go(a)) return 1;
		return 2;
	}

	void reverse(int [] a) {
		for (int i = 0; i < a.length / 2; i++) {
			int t = a[i];
			a[i] = a[a.length - i - 1];
			a[a.length - i - 1] = t;
		}
	}

	int notzeros(int [] a, int l, int r) {
		int ret = 0;
		for (int i = l; i <= r; i++) {
			if (a[i] != 0) {
				ret++;
			}
		}
		return ret;
	}

	public void run() {
		try {
			Locale.setDefault(Locale.US);
			in = local ? new BufferedReader(new FileReader("input.txt")) : new BufferedReader(new InputStreamReader(System.in));
			out = local ? new PrintStream(new File("output.txt")) : new PrintStream(System.out);

			n = nextInt();
			int [] a = new int[n];
			for (int i = 0; i < n; i++) {
				a[i] = nextInt();
			}

			if (n == 1) printExit("0");
			if (good(a, 0, n - 1)) printExit("0");

			for (int i = 0; i < n; i++) {
				if (a[i] == 0) {
					int [] arr = new int[n - 1];
					for (int j = 0; j < i; j++) arr[j] = a[j];
					for (int j = i + 1; j < n; j++) arr[j - 1] = a[j];
					if (good(arr, 0, n - 2)) printExit("1");
					reverse(arr);
					if (good(arr, 0, n - 2)) printExit("1");

					// may assume b = 0
					int z = notzeros(a, 1, n - 1);
					if (z == 1) printExit("1");
					printExit("2");			
				}
			}

			int g1 = get(a);
			reverse(a);
			int g2 = get(a);

			out.println(min(g1, g2));
		}
		catch (Exception e) {
			e.printStackTrace();
		}
	}

	boolean seekForToken() {
 		try {
			while (!st.hasMoreTokens()) {
				String s = in.readLine();
				if (s == null) {
				 	return false;
				}
			 	st = new StringTokenizer(s);
			}
			return true;
		}
		catch (IOException e) {
		 	e.printStackTrace();
		 	return false;
		}
 	}

 	int nextInt() {
		return Integer.parseInt(nextToken());
 	}

 	long nextLong() {
		return Long.parseLong(nextToken());
 	}

 	double nextDouble() {
		return Double.parseDouble(nextToken());
 	}

 	BigInteger nextBigInteger() {
 	 	return new BigInteger(nextToken());
 	}

 	String nextToken() {
 	 	seekForToken();
 	 	return st.nextToken();
 	}

}
