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. 
/* Codeforces Template */

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 {
	
	static long initTime;
	static final Random rnd = new Random(7777L);
	static boolean writeLog = false;
	
	public static void main(String[] args) throws IOException {
		initTime = System.currentTimeMillis();
		try {
			writeLog = "true".equals(System.getProperty("LOCAL_RUN_7777"));
		} catch (SecurityException e) {}
		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) {}
					long prevTime = System.currentTimeMillis();
					new Main().run();
					log("Total time: " + (System.currentTimeMillis() - prevTime) + " ms");
					log("Memory status: " + memoryStatus());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
		}, "1", 1L << 24).start(); 
	}

	void run() throws IOException {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		solve();
		out.close();
		in.close();
	}
	
	/*************************************************************** 
	 * Solution
	 **************************************************************/

	int n;
	int[] a;
	
	int fullMask;
	int rNum;
	
	Set<Long> used = new HashSet<Long>();
	
	void solve() throws IOException  {
		
		n = nextInt();
		a = nextIntArray(n);
		
		int x = a[0];
		for (int i = 0; i < n; i++) {
			if (x > a[i]) {
				x = a[i];
			}
		}
		
		fullMask = (1 << n) - 1;
		
		for (int i = 0; i < n; i++) {
			if (a[i] % x != 0) {
				out.println(-1);
				return;
			}
			a[i] /= x;
		}

		for (rNum = 1; ; rNum++) {
			used.clear();

			if (rNum > n) {
				out.println(-1);
				return;
			}
			
			if (rec(1, 1)) {
				out.println(rNum);
				return;
			}
		}
	
	}
	
	boolean rec(int maskHave, int maskVisited) {
		
		if (maskVisited == fullMask) return true;
		
		int bc = Integer.bitCount(maskHave);
		if (bc > rNum) return false;
		
		long state = (((long) maskHave) << 25) | maskVisited;
		if (used.contains(state))
			return false;
		used.add(state);

		int t = Integer.bitCount(maskVisited);
		
		for (int i = 0; i < n; i++) {
			
			if ((maskHave & (1 << i)) == 0) continue;
			
			for (int j = i; j < n; j++) {
				
				if ((maskHave & (1 << j)) == 0) continue;
				
				if (a[i] + a[j] != a[t]) continue;
				
				int bitHave = 1 << t;
				if ((maskVisited & bitHave) != 0) continue;
				
				int nMaskVisited = maskVisited | bitHave;
				int nMaskHave = maskHave | bitHave;
				
				if (bc < rNum && rec(nMaskHave, nMaskVisited)) return true;
				
				for (int k = 0; k < n; k++) {
					int cbit = 1 << k;
					if ((maskHave & cbit) != 0) {
						if (rec(nMaskHave & (~cbit), nMaskVisited))
							return true;
					}
				}
			}
		}
		
		return false;
	}

	/*************************************************************** 
	 * Input 
	 **************************************************************/
	BufferedReader in;
	PrintWriter out;
	StringTokenizer st = new StringTokenizer("");
	
	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());
	}
	
	int[] nextIntArray(int size) throws IOException {
		int[] ret = new int [size];
		for (int i = 0; i < size; i++)
			ret[i] = nextInt();
		return ret;
	}
	
	long[] nextLongArray(int size) throws IOException {
		long[] ret = new long [size];
		for (int i = 0; i < size; i++)
			ret[i] = nextLong();
		return ret;
	}
	
	double[] nextDoubleArray(int size) throws IOException {
		double[] ret = new double [size];
		for (int i = 0; i < size; i++)
			ret[i] = nextDouble();
		return ret;
	}
	
	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;
	}
	
	/*************************************************************** 
	 * Output 
	 **************************************************************/
	void printRepeat(String s, int count) {
		for (int i = 0; i < count; i++)
			out.print(s);
	}
	
	void printArray(int[] array) {
		if (array == null || array.length == 0)
			return;
		for (int i = 0; i < array.length; i++) {
			if (i > 0) out.print(' ');
			out.print(array[i]);
		}
		out.println();
	}
	
	void printArray(long[] array) {
		if (array == null || array.length == 0)
			return;
		for (int i = 0; i < array.length; i++) {
			if (i > 0) out.print(' ');
			out.print(array[i]);
		}
		out.println();
	}
	
	void printArray(double[] array) {
		if (array == null || array.length == 0)
			return;
		for (int i = 0; i < array.length; i++) {
			if (i > 0) out.print(' ');
			out.print(array[i]);
		}
		out.println();
	}
	
	void printArray(double[] array, String spec) {
		if (array == null || array.length == 0)
			return;
		for (int i = 0; i < array.length; i++) {
			if (i > 0) out.print(' ');
			out.printf(Locale.US, spec, array[i]);
		}
		out.println();
	}
	
	void printArray(Object[] array) {
		if (array == null || array.length == 0)
			return;
		boolean blank = false;
		for (Object x : array) {
			if (blank) out.print(' '); else blank = true;
			out.print(x);
		}
		out.println();
	}
	
	@SuppressWarnings("rawtypes")
	void printCollection(Collection collection) {
		if (collection == null || collection.isEmpty())
			return;
		boolean blank = false;
		for (Object x : collection) {
			if (blank) out.print(' '); else blank = true;
			out.print(x);
		}
		out.println();
	}
	
	/*************************************************************** 
	 * Utility
	 **************************************************************/
	static String memoryStatus() {
		return (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory() >> 20) + "/" + (Runtime.getRuntime().totalMemory() >> 20) + " MB";
	}
	
	static void checkMemory() {
		System.err.println(memoryStatus());
	}
	
	static long prevTimeStamp = Long.MIN_VALUE;
	
	static void updateTimer() {
		prevTimeStamp = System.currentTimeMillis();
	}
	
	static long elapsedTime() {
		return (System.currentTimeMillis() - prevTimeStamp);
	}
	
	static void checkTimer() {
		System.err.println(elapsedTime() + " ms");
	}
	
	static void chk(boolean f) {
		if (!f) throw new RuntimeException("Assert failed");
	}
	
	static void chk(boolean f, String format, Object ... args) {
		if (!f) throw new RuntimeException(String.format(format, args));
	}
	
	static void log(String format, Object ... args) {
		if (writeLog) System.err.println(String.format(Locale.US, format, args));
	}
}
