CF1005C Summarize to the Power of Two

A sequence $ a_1, a_2, \dots, a_n $ is called good if, for each element $ a_i $ , there exists an element $ a_j $ ( $ i \ne j $ ) such that $ a_i+a_j $ is a power of two (that is, $ 2^d $ for some non-negative integer $ d $ ). For example, the following sequences are good: - $ [5, 3, 11] $ (for example, for $ a_1=5 $ we can choose $ a_2=3 $ . Note that their sum is a power of two. Similarly, such an element can be found for $ a_2 $ and $ a_3 $ ), - $ [1, 1, 1, 1023] $ , - $ [7, 39, 89, 25, 89] $ , - $ [] $ . Note that, by definition, an empty sequence (with a length of $ 0 $ ) is good. For example, the following sequences are not good: - $ [16] $ (for $ a_1=16 $ , it is impossible to find another element $ a_j $ such that their sum is a power of two), - $ [4, 16] $ (for $ a_1=4 $ , it is impossible to find another element $ a_j $ such that their sum is a power of two), - $ [1, 3, 2, 8, 8, 8] $ (for $ a_3=2 $ , it is impossible to find another element $ a_j $ such that their sum is a power of two). You are given a sequence $ a_1, a_2, \dots, a_n $ . What is the minimum number of elements you need to remove to make it good? You can delete an arbitrary set of elements.

The first line contains the integer $ n $ ( $ 1 \le n \le 120000 $ ) — the length of the given sequence. The second line contains the sequence of integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^9 $ ).

Print the minimum number of elements needed to be removed from the given sequence in order to make it good. It is possible that you need to delete all $ n $ elements, make it empty, and thus get a good sequence.

In the first example, it is enough to delete one element $ a_4=5 $ . The remaining elements form the sequence $ [4, 7, 1, 4, 9] $ , which is good.