The Minimum Number of Variables
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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.

输入描述:

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.

输出描述:

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.

示例1

输入

复制 
5
1 2 3 6 8

输出

复制 
2
示例2

输入

复制 
3
3 6 5

输出

复制 
-1
示例3

输入

复制 
6
2 4 8 6 10 18

输出

复制 
3

备注:

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


    
 
  1. b1:=1; 
    2. 
 
  2. b2:=b1 + b1; 
    3. 
 
  3. b1:=b1 + b2; 
    4. 
 
  4. b1:=b1 + b1; 
    5. 
 
  5. b1:=b1 + b2. 
    6.