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 java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Diego Huerfano ( diego.link )
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		OutputWriter out = new OutputWriter(outputStream);
		TaskD solver = new TaskD();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskD {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        final int n=in.readInt();
        int a[]=in.readInts( n );
        int needed[][]=new int[n][n];
        for( int i=0; i<n; i++ ) {
            Arrays.fill( needed[i], 0, i, -1 );
            for( int j=0; j<i; j++ ) {
                for( int k=0; k<i; k++ ){
                    if( a[j]+a[k]==a[i] )
                        needed[i][j]=k;
                }
            }
        }
        boolean possible[][]=new boolean[2][1<<n];
        Arrays.fill( possible[0], true );
        int i1=1, i2=0;
        boolean ok;
        for( int i=1; i<n; i++ ) {
            Arrays.fill( possible[i1], 0, 1<<i, false );
            for( int mask=0; mask<(1<<i); mask++ ) {
                ok=false;
                for( int j=0; j<i && !possible[i1][mask]; j++ )
                    if( needed[i][j]!=-1 && ( (mask&(1<<j))!=0 || (needed[i][j]==j) ) ) {
                        if( (mask&(1<<needed[i][j]))==0 && ( (mask|(1<<needed[i][j])) & (1<<(i-1)) )!=0 )
                            possible[i1][mask]|=possible[i2][(mask|(1<<needed[i][j]))-(1<<(i-1))];
                        else if( (mask&(1<<needed[i][j]))!=0 )
                            ok=true;
                    }
                if( ok && !possible[i1][mask] ) {
                    for( int j=0; j<i; j++ )
                        if( ( (mask|(1<<j)) & (1<<(i-1)) )!=0 )
                            possible[i1][mask]|=possible[i2][(mask|(1<<j))-(1<<(i-1))];
                }
            }
            i1=1-i1;
            i2=1-i1;
        }

        int answer=Integer.MAX_VALUE;
        for( int mask=0; mask<(1<<(n-1)); mask++ )
            if( possible[i2][mask] ) {
                answer=Math.min( answer, Integer.bitCount( mask )+1 );
            }
        if( answer==Integer.MAX_VALUE ) out.printLine( -1 );
        else out.printLine( answer );
    }
}

class InputReader {

    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private SpaceCharFilter filter;

    public InputReader(InputStream stream) {
        this.stream = stream;
    }

    public int read() {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    public int readInt() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public int[] readInts( int n ){
        int ans[]=new int[n];
        for( int i=0; i<n; i++ ) ans[i]=readInt();
        return ans;
    }

    public boolean isSpaceChar(int c) {
        if (filter != null)
            return filter.isSpaceChar(c);
        return isWhitespace(c);
    }

    public static boolean isWhitespace(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public interface SpaceCharFilter {
        public boolean isSpaceChar(int ch);
    }
}

class OutputWriter {
    private final PrintWriter writer;

    public OutputWriter(OutputStream outputStream) {
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public OutputWriter(Writer writer) {
        this.writer = new PrintWriter(writer);
    }

    public void print(Object...objects) {
        for (int i = 0; i < objects.length; i++) {
            if (i != 0)
                writer.print(' ');
            writer.print(objects[i]);
        }
    }

    public void printLine(Object...objects) {
        print( objects );
        writer.println();
    }

    public void close() {
        writer.close();
    }
}

