You've got a positive integer sequence a1, a2, ..., an. All numbers in the sequence are distinct. Let's fix the set of variables b1, b2, ..., bm. Initially each variable bi (1 ≤ i ≤ m) contains the value of zero. Consider the following sequence, consisting of n operations.

The first operation is assigning the value of a1 to some variable bx (1 ≤ x ≤ m). Each of the following n - 1 operations is assigning to some variable by the value that is equal to the sum of values that are stored in the variables bi and bj (1 ≤ i, j, y ≤ m). At that, the value that is assigned on the t-th operation, must equal at. For each operation numbers y, i, j are chosen anew.

Your task is to find the minimum number of variables m, such that those variables can help you perform the described sequence of operations.

Input

The first line contains integer n (1 ≤ n ≤ 23). The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ak ≤ 109).

It is guaranteed that all numbers in the sequence are distinct.

Output

In a single line print a single number — the minimum number of variables m, such that those variables can help you perform the described sequence of operations.

If you cannot perform the sequence of operations at any m, print -1.

Examples

Input

5
1 2 3 6 8


Output

2


Input

3
3 6 5


Output

-1


Input

6
2 4 8 6 10 18


Output

3

Note

In the first sample, you can use two variables b1 and b2 to perform the following sequence of operations.

  1. b1 := 1; 
  2. b2 := b1 + b1; 
  3. b1 := b1 + b2; 
  4. b1 := b1 + b1; 
  5. b1 := b1 + b2. 
import static java.lang.Math.*;
import static java.math.BigInteger.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;

import java.io.*;
import java.lang.reflect.*;
import java.util.*;

public class D {

	final static boolean autoflush = false;
	
	final static int INF = (int) 1e9;
	
	Integer [] A;
	int N; 
	int [] Q; 
	int [][] R;
	
	public D () {
		N = sc.nextInt();
		A = sc.nextInts();
		
		if (N == 1)
			exit(1);
		
		next: for (int i : rep(1, N)) {
			for (int j : rep(i)) 
				for (int k : rep(i))
					if (A[j] + A[k] == A[i])
						continue next;
			exit(-1);
		}
		
		Map<Integer, Integer> M = new TreeMap<Integer, Integer>();
		for (int i : rep(N))
			M.put(A[i], i);

		Q = new int [N];
		R = new int [N][N];
		
		for (int i : rep(N))
			for (int j : rep(i))
				if (M.containsKey(A[i] - A[j])) {
					int k = M.get(A[i] - A[j]);
					Q[i] |= (1 << j);
					R[i][j] = k;
				}

		H = new int [1 << (N-1)]; fill(H, -1);
		
		int res = solve(1, 1);
		assert res <= N - N/3;
		exit(res);
	}
		
	int [] H;
	
	int solve(int X, int J) {
		int B = (X & Q[J]);
		if (B == 0)
			return H[X] = INF;
		
		for (int i = 0; i < J; ++i) {
			int U = (1 << i), V = (1 << R[J][i]);
			if ((B&U) != 0 && (B&V) != 0)
				break;
			if (i == J-1)
				return H[X] = INF;
		}
		
		if (J == N-1)
			return H[X] = Integer.bitCount(X);
		
		int Y = (X | (1 << J)), res = INF;
		for (int j = 0; j < J; ++j) {
			int W = (1 << j);
			if ((Y & W) != 0) {
				int V = Y & (~W), R = H[V] == -1 ? solve(V, J+1) : H[V];
				res = min(res, R);
			}
		}
		
		if (Integer.bitCount(Y) <= 8) {
			int R = H[Y] == -1 ? solve(Y, J+1) : H[Y];
			res = min(res, R);
		}
		return H[X] = res;		
	}

	////////////////////////////////////////////////////////////////////////////////////

	static int [] rep(int N) { return rep(0, N); }
	static int [] rep(int S, int T) { int [] res = new int [T-S]; for (int i = S; i < T; ++i) res[i-S] = i; return res; }
	static int [] req(int S, int T) { return rep(S, T+1); }	

	////////////////////////////////////////////////////////////////////////////////////

	/* Dear hacker, don't bother reading below this line, unless you want to help me debug my I/O routines :-) */
	
	final static MyScanner sc = new MyScanner();
	
	static class MyScanner {
		public String next() {
			newLine();
			return line[index++];
		}
		
		public char nextChar() {
			return next().charAt(0);
		}
				
		public int nextInt() {
			return Integer.parseInt(next());
		}
		
		public long nextLong() {
			return Long.parseLong(next());
		}
		
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		
		public String nextLine() {
			line = null;
			return readLine();
		}
		
		public String [] nextStrings() {
			line = null;
			return readLine().split(" ");
		}
		
		public char [] nextChars() {
			return next ().toCharArray ();
		}

		public Integer [] nextInts() {
			String [] L = nextStrings();
			Integer [] res = new Integer [L.length];
			for (int i : rep(L.length))
				res[i] = Integer.parseInt(L[i]);
			return res;
		}	
		
		public Long [] nextLongs() {
			String [] L = nextStrings();
			Long [] res = new Long [L.length];
			for (int i : rep(L.length))
				res[i] = Long.parseLong(L[i]);
			return res;
		}

		public Double [] nextDoubles() {
			String [] L = nextStrings();
			Double [] res = new Double [L.length];
			for (int i : rep(L.length))
				res[i] = Double.parseDouble(L[i]);
			return res;
		}

		public String [] next (int N) {
			String [] res = new String [N];
			for (int i : rep(N))
				res[i] = sc.next();
			return res;
		}
		
		public Integer [] nextInt (int N) {
			Integer [] res = new Integer [N];
			for (int i : rep(N))
				res[i] = sc.nextInt();
			return res;
		}		
		
		public Long [] nextLong (int N) {
			Long [] res = new Long [N];
			for (int i : rep(N))
				res[i] = sc.nextLong();
			return res;
		}		
		
		public Double [] nextDouble (int N) {
			Double [] res = new Double [N];
			for (int i : rep(N))
				res[i] = sc.nextDouble();
			return res;
		}		
		
		public String [][] nextStrings (int N) {
			String [][] res = new String [N][];
			for (int i : rep(N))
				res[i] = sc.nextStrings();
			return res;
		}
		
		public Integer [][] nextInts (int N) {
			Integer [][] res = new Integer [N][];
			for (int i : rep(N))
				res[i] = sc.nextInts();
			return res;
		}
		
		public Long [][] nextLongs (int N) {
			Long [][] res = new Long [N][];
			for (int i : rep(N))
				res[i] = sc.nextLongs();
			return res;
		}
		
		public Double [][] nextDoubles (int N) {
			Double [][] res = new Double [N][];
			for (int i : rep(N))
				res[i] = sc.nextDoubles();
			return res;
		}
		
		//////////////////////////////////////////////
		
		private boolean eol() {
			return index == line.length;
		}

		private String readLine() {
			try {
				return r.readLine();
			} catch (Exception e) {
				throw new Error (e);
			}
		}
		private final BufferedReader r;

		MyScanner () {
			this(new BufferedReader(new InputStreamReader(System.in)));
		}
		
		MyScanner (BufferedReader r) {
			try {
				this.r = r;
				while (!r.ready())
					Thread.sleep(1);
				start();
			} catch (Exception e) {
				throw new Error(e);
			}
		}
		
		private String [] line;
		private int index;

		private void newLine() {
			if (line == null || eol()) {
				line = readLine().split(" ");
				index = 0;
			}
		}		
	}
	
	static void print (Object o, Object... a) {
		printDelim(" ", o, a);
	}
	
	static void cprint (Object o, Object... a) {
		printDelim("", o, a);
	}
	
	static void printDelim (String delim, Object o, Object... a) {
		pw.println(build(delim, o, a));
	}

	static void exit (Object o, Object... a) {
		print(o, a);
		exit();
	}

	static void exit() {
		pw.close();
		System.out.flush();
		System.err.println("------------------");
		System.err.println("Time: " + ((millis() - t) / 1000.0));
		System.exit(0);
	}
	
	static void NO() {
		throw new Error("NO!");
	}
	
	////////////////////////////////////////////////////////////////////////////////////
	
	static String build (String delim, Object o, Object... a) {
		StringBuilder b = new StringBuilder();
		append(b, o, delim);
		for (Object p : a)
			append(b, p, delim);
		return b.toString().trim();		
	}
	
	static void append(StringBuilder b, Object o, String delim) {
		if (o.getClass().isArray()) {
			int L = Array.getLength(o);
			for (int i : rep(L))
				append(b, Array.get(o, i), delim);
		} else if (o instanceof Iterable<?>) {
			for (Object p : (Iterable<?>)o)
				append(b, p, delim);
		} else
			b.append(delim).append(o);		
	}
	
	////////////////////////////////////////////////////////////////////////////////////
	
	static void statics() {
		abs(0);
		valueOf(0);
		asList(new Object [0]);
		reverseOrder();
	}
	
	public static void main (String[] args) {
		new D();
		exit();
	}

	static void start() {
		t = millis();
	}

	static PrintWriter pw = new PrintWriter(System.out, autoflush);
	
	static long t;
	
	static long millis() {
		return System.currentTimeMillis();
	}	
}
