题目背景

2025 年海淀区中小学生信息学竞赛小学组复赛题目，数据为洛谷自造。

为更好区分不同时间复杂度的做法，本题时间限制下调到 500 毫秒。

题目描述

陶陶是一个计算机爱好者，对二进制数有着特别的喜好，遇到各种各样的数据，他总能找到跟 $2$ 的整数次幂的关系。现在，他获得了一个长度为 $n$ 的数列 $a_1, a_2, \dots, a_n$，他发现其中有些元素的和恰好是 $2$ 的整数次幂。对于给定的 $a_1, a_2, \dots, a_n$，你的任务是统计有多少个数对 $(i, j)$ 满足 $a_i + a_j = 2^x$，其中 $x \in \N^*$，$i < j$，这里 $\N^*$ 表示正整数集合。

输入格式

第一行包含一个整数 $n$，第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$。

输出格式

仅有一个正整数，表示满足 $a_i + a_j$ 是 $2$ 的整数次幂的数对 $(i, j)$ 的个数。

4
7 3 2 1

2

3
1 1 1

3

提示

• 对于 $40\%$ 的数据，$1 \leq n \leq 10^3$，对于每一个正整数 $i$，$1 \leq i \leq n$，都有 $1 \leq a_i \leq 10^9$。
• 对于另外 $60\%$ 的数据，$1 \leq n \leq 10^5$，对于每一个正整数 $i$，$1 \leq i \leq n$，都有 $1 \leq a_i \leq 10^9$。