Summarize to the Power of Two

题意翻译

给出一个长度为 $n$ 的序列 $a$，求最少删除多少个数使 $\forall i$，$\exists j\ne i,a_i+a_j$ 为 $2$ 的幂次方。

题目描述

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.

输入输出样例

输入样例 #1

6
4 7 1 5 4 9

输出样例 #1

1

输入样例 #2

5
1 2 3 4 5

输出样例 #2

2

输入样例 #3

1
16

输出样例 #3

1

输入样例 #4

4
1 1 1 1023

输出样例 #4

0

说明

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.