P6196 - The Minimum Number of Variables

内存限制：256 MB 时间限制：2 S

题面：传统评测方式：文本比较上传者：

提交：0 通过：0

You've got a positive integer sequence a₁,a₂,...,a_n. All numbers in the sequence are distinct. Let's fix the set of variables b₁,b₂,...,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₁ 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₁,a₂,...,a_n (1≤a_k≤10⁹).

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

Input

3
3 6 5

Output

-1

Input

6
2 4 8 6 10 18

Output

Note

In the first sample, you can use two variables b₁ and b₂ to perform the following sequence of operations.

b₁ := 1;
b₂ := b₁+b₁;
b₁ := b₁+b₂;
b₁ := b₁+b₁;
b₁ := b₁+b₂.

6196: The Minimum Number of Variables

题目描述