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.

输入描述:

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.

备注:

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