|Codeforces Round #496 (Div. 3)|
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:
Note that, by definition, an empty sequence (with a length of $$$0$$$) is good.
For example, the following sequences are not good:
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.
4 7 1 5 4 9
1 2 3 4 5
1 1 1 1023
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.