你有一个正整数序列 a1, a2, ..., an。序列中的所有数字都是不同的。让我们修复变量集 b1, b2, ..., bm。最初,每个变量 bi (1 ≤ i ≤ m) 包含零值。考虑以下由 n 个操作组成的序列。
第一个操作是将 a1 的值分配给某个变量 bx (1 ≤ x ≤ m)。以下 n - 1 个操作中的每一个都将值分配给某个变量,该值等于存储在变量 bi 和 bj 中的值之和 (1 ≤ i, j, y ≤ m)。此时,在第 t 次操作中分配的值必须等于 at。对于每个操作,重新选择数字 y、i、j。
你的任务是找到变量 m 的最小数量,以便这些变量可以帮助你执行所描述的操作序列。
输入
第一行包含整数 n (1 ≤ n ≤ 23)。第二行包含 n 个空格分隔的整数 a1, a2, ..., an (1 ≤ ak ≤ 109)。
保证序列中的所有数字都是不同的。
输出
在一行中打印一个数字 - 变量 m 的最小数量,这样这些变量可以帮助您执行所描述的操作序列。
如果在任何 m 处都无法执行操作序列,则打印 -1。
示例
输入 #1
5 1 2 3 6 8
输出 #1
2
输入 #2
3 3 6 5
输出 #2
-1
输入 #3
6 2 4 8 6 10 18
输出 #3
3
注意
在第一个示例中,您可以使用两个变量 b1 和 b2 来执行以下操作序列。
1. b1 := 1;
2. b2 := b1 + b1;
3. b1 := b1 + b2;
4. b1 := b1 + b1;
5. b1 := b1 + b2。