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
/**
 * Created by IntelliJ IDEA.
 * User: piyushd
 * Date: 12/28/10
 * Time: 11:51 PM
 * To change this template use File | Settings | File Templates.
 */
public class GP {

    void run(){
		int N = nextInt();

		int[] a = new int[N];
		for(int i = 0; i < N; i++) a[i] = nextInt();

		int[] zero = new int[N];
		int[] nonzero = new int[N];
		int z = 0, nz = 0;
		for(int i = 0; i < N; i++)
			if(a[i] == 0)zero[z++] = i;
			else nonzero[nz++] = i;

		if(nz == 0){
			System.out.println(0); return;
		}
		if(nz == 1){
			if(nonzero[0] == 0) System.out.println(0);
			else System.out.println(1);
			return;
		}
		if(nz == 2 && z > 0){
			if(nonzero[0] == 0) System.out.println(1);
			else System.out.println(2);
			return;
		}
		if(z > 0){
			if(z > 1){
				System.out.println(2); return;
			}
			if(valid(a, zero[0])) System.out.println(1);
			else System.out.println(2);
			return;
		}

		if(valid(a, -1)){
			System.out.println(0); return;
		}

		int cnt = 0;
		for(int i = 0; i < N - 2; i++){
			if(a[i + 1] * a[i + 1] != a[i] * a[i + 2]) {
				cnt++;
				if(cnt > 3) {
					System.out.println(2); return;
				}
				if(valid(a, i) || valid(a, i + 1) || valid(a, i + 2)){
					System.out.println(1); return;
				}
			}
		}
		System.out.println(2);
    }

	boolean valid(int[] a, int not){
		int first = 0, second = 0;
		for(int i = 0; i < a.length; i++){
			if(i == not) continue;
			if(first != 0){
				if(first * a[i] != second * second) return false;
			}
			first = second;
			second = a[i];
		}
		return true;
	}

    int nextInt(){
        try{
            int c = System.in.read();
            if(c == -1) return c;
            while(c != '-' && (c < '0' || '9' < c)){
                c = System.in.read();
                if(c == -1) return c;
            }
            if(c == '-') return -nextInt();
            int res = 0;
            do{
                res *= 10;
                res += c - '0';
                c = System.in.read();
            }while('0' <= c && c <= '9');
            return res;
        }catch(Exception e){
            return -1;
        }
    }

    long nextLong(){
        try{
            int c = System.in.read();
            if(c == -1) return -1;
            while(c != '-' && (c < '0' || '9' < c)){
                c = System.in.read();
                if(c == -1) return -1;
            }
            if(c == '-') return -nextLong();
            long res = 0;
            do{
                res *= 10;
                res += c-'0';
                c = System.in.read();
            }while('0' <= c && c <= '9');
            return res;
        }catch(Exception e){
            return -1;
        }
    }

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

    String next(){
        try{
            StringBuilder res = new StringBuilder("");
            int c = System.in.read();
            while(Character.isWhitespace(c))
                c = System.in.read();
            do{
                res.append((char)c);
            }while(!Character.isWhitespace(c=System.in.read()));
            return res.toString();
        }catch(Exception e){
            return null;
        }
    }

    String nextLine(){
        try{
            StringBuilder res = new StringBuilder("");
            int c = System.in.read();
            while(c == '\r' || c == '\n')
                c = System.in.read();
            do{
                res.append((char)c);
                c = System.in.read();
            }while(c != '\r' && c != '\n');
            return res.toString();
        }catch(Exception e){
            return null;
        }
    }

    public static void main(String[] args){
        new GP().run();
    }
}
