#1101. Summarize to the Power of Two (※※)

    ID: 1101 远端评测题 3000ms 256MiB 尝试: 54 已通过: 8 难度: 8 上传者: 标签>brute forcegreedyimplementation*1300btranslated

Summarize to the Power of Two (※※)

题目描述

如果对于每个元素aia_i,存在一个元素aja_jiji \ne j),使得ai+aja_i+a_j是 2 的幂次(即对于某个非负整数dd2d2^d是 2 的幂次),那么序列a1,a2,,ana_1, a_2, \dots, a_n被称为好序列。

例如,下列序列就很好:

  • [5,3,11][5, 3, 11](例如,对于 a1=5a_1=5,我们可以选择 a2=3a_2=3。注意它们的和是 2 的幂。同样,也可以为 a2a_2a3a_3 找到这样的元素、)
  • [1,1,1,1023][1, 1, 1, 1023],
  • [7,39,89,25,89][7, 39, 89, 25, 89],
  • [][].

注意,根据定义,空序列(长度为 00)是好序列。

例如,以下序列不是好序列:

  • [16][16](对于 a1=16a_1=16,不可能找到另一个元素 aja_j,使得它们的和是 2 的幂次)、
  • [4,16][4, 16](对于a1=4a_1=4,不可能找到另一个元素aja_j使它们的和是二的幂次)、
  • [1,3,2,8,8,8][1, 3, 2, 8, 8, 8](对于a3=2a_3=2,不可能找到另一个元素aja_j使它们的和是二的幂次)。

给你一个序列 a1,a2,,ana_1, a_2, \dots, a_n。要使它变好,至少需要删除多少个元素?你可以删除任意一组元素。

输入描述

第一行包含整数 nn1n1200001 \le n \le 120000)--给定序列的长度。

第二行包含整数序列 a1,a2,,ana_1, a_2, \dots, a_n1ai1091 \le a_i \le 10^9)。

输出描述

打印从给定序列中删除的最小元素数,以使其成为一个好序列。有可能需要删除所有 nn个元素,使其为空,从而得到一个良好的序列。

样例

6
4 7 1 5 4 9
1
5
1 2 3 4 5
2
1
16
1
4
1 1 1 1023
0

说明

在第一个例子中,只需删除一个元素a4=5a_4=5即可。其余元素构成序列 [4,7,1,4,9][4, 7, 1, 4, 9],这很好。