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 a 1 , a 2 , ..., a n (1 ≤ a k ≤ 10 9 ) . 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 b 1 and b 2 to perform the following sequence of operations. b 1 := 1 ; b 2 := b 1 + b 1 ; b 1 := b 1 + b 2 ; b 1 := b 1 + b 1 ; b 1 := b 1 + b 2 .