You've got a positive integer sequence $*a*_{1}, *a*_{2}, ..., *a*_{*n*}$. All numbers in the sequence are distinct. Let's fix the set of variables $*b*_{1}, *b*_{2}, ..., *b*_{*m*}$. Initially each variable $*b*_{*i*}$ $(1 ≤ *i* ≤ *m*)$ contains the value of zero. Consider the following sequence, consisting of $*n*$ operations.

The first operation is assigning the value of $*a*_{1}$ to some variable $*b*_{*x*}$ $(1 ≤ *x* ≤ *m*)$. Each of the following $*n* - 1$ operations is assigning to some variable $*b*_{*y*}$ the value that is equal to the sum of values that are stored in the variables $*b*_{*i*}$ and $*b*_{*j*}$ $(1 ≤ *i*, *j*, *y* ≤ *m*)$. At that, the value that is assigned on the $*t*$-th operation, must equal $*a*_{*t*}$. 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 $*a*_{1}, *a*_{2}, ..., *a*_{*n*}$ $(1 ≤ *a*_{*k*} ≤ 10^{9})$.

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.

Note

In the first sample, you can use two variables $*b*_{1}$ and $*b*_{2}$ to perform the following sequence of operations.

1. $*b*_{1}$ := $1$;
2. $*b*_{2}$ := $*b*_{1} + *b*_{1}$;
3. $*b*_{1}$ := $*b*_{1} + *b*_{2}$;
4. $*b*_{1}$ := $*b*_{1} + *b*_{1}$;
5. $*b*_{1}$ := $*b*_{1} + *b*_{2}$.