Последовательность \(a_1, a_2, \dots, a_n\) называется хорошей, если для любого его элемента \(a_i\) найдется такой элемент \(a_j\) (\(i \ne j\)), что \(a_i+a_j\) является степенью двойки (то есть равен \(2^d\) для некоторого неотрицательного целого \(d\)).
Например, следующие последовательности — хорошие:
- \([5, 3, 11]\) (например, для \(a_1=5\) можно выбрать \(a_2=3\), что сумма — степень двойки, подобную пару можно найти и для \(a_2\) и \(a_3\)),
- \([1, 1, 1, 1023]\),
- \([7, 39, 89, 25, 89]\),
- \([]\).
Обратите внимание, что по определению пустая последовательность (то есть такая, длина которой равна \(0\)) является хорошей.
Например, следующие последовательности не являются хорошими:
- \([16]\) (для \(a_1=16\) невозможно найти другой элемент \(a_j\), что их сумма — степень двойки),
- \([4, 16]\) (для \(a_1=4\) невозможно найти другой элемент \(a_j\), что их сумма — степень двойки),
- \([1, 3, 2, 8, 8, 8]\) (для \(a_3=2\) невозможно найти другой элемент \(a_j\), что их сумма — степень двойки).
Задана последовательность \(a_1, a_2, \dots, a_n\). Какое наименьшее количество элементов надо удалить, чтобы сделать её хорошей? Удалять можно произвольный набор элементов.
Выходные данные
Выведите наименьшее количество элементов, которые надо удалить из заданной последовательности, чтобы сделать её хорошей. Это допустимый случай, что придётся удалить все \(n\) элементов, сделать её пустой и таким образом получить хорошую последовательность.
Примечание
В первом примере достаточно удалить один элемент \(a_4=5\). Оставшиеся элементы образуют последовательность \([4, 7, 1, 4, 9]\), которая является хорошей.