D. Минимальное количество переменных
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Вам задана последовательность положительных целых чисел a1, a2, ..., an. Все числа в последовательности различны. Зафиксируем набор переменных b1, b2, ..., bm. Изначально в каждой переменной bi (1 ≤ i ≤ m) хранится значение нуль. Рассмотрим следующую последовательность, состоящую из n операций.

Первая операция состоит в том, чтобы присвоить какой-то переменной bx (1 ≤ x ≤ m) значение, равное a1. Каждая из следующих n - 1 операций состоит в том, чтобы присвоить какой-то переменной by значение, равное сумме значений, хранящихся в переменных 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.

Примеры
Входные данные
5
1 2 3 6 8
Выходные данные
2
Входные данные
3
3 6 5
Выходные данные
-1
Входные данные
6
2 4 8 6 10 18
Выходные данные
3
Примечание

В первом примере можно при помощи двух переменных b1 и b2 произвести следующую последовательность операций.

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