CF279D.The Minimum Number of Variables

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.

你有一个正整数序列 $a_1, a_2, \dots, a_n$，其中所有数互不相同。现固定一组变量 $b_1, b_2, \dots, b_m$。初始时，每个变量 $b_i$（$1 \le i \le m$）的值均为 $0$。考虑如下由 $n$ 个操作构成的序列：

• 第一个操作是将 $a_1$ 的值赋给某个变量 $b_x$（$1 \le x \le m$）；
• 后续的 $n-1$ 个操作中，每个操作均将某变量 $b_y$（$1 \le y \le m$）赋值为另外两个变量 $b_i$ 与 $b_j$（$1 \le i, j \le m$）当前所存数值之和；
• 此外，第 $t$ 个操作所赋的值必须恰好等于 $a_t$（$1 \le t \le n$）；
• 每次操作中，下标 $y, i, j$ 均可重新选择。

你的任务是：求出满足上述操作序列所需的最小变量个数 $m$。

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 ≤ 109).

It is guaranteed that all numbers in the sequence are distinct.

第一行包含一个整数 $n$（$1 \leq n \leq 23$）。第二行包含 $n$ 个以空格分隔的整数 $a_1,\,a_2,\,...,\,a_n$（$1 \leq a_k \leq 10^9$）。

保证序列中所有数字互不相同。

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.

在一行中输出一个整数——能够完成所述操作序列所需的最少变量数 $m$。

如果无论取何值的 $m$ 都无法完成该操作序列，则输出 $-1$。

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.

在第一个样例中，你可以使用两个变量 $b_1$ 和 $b_2$ 执行以下操作序列：

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$。