cf 702B

You are given n integers a1, a2, ..., an. Find the number of pairs of indexes i, j (i < j) that ai + aj is a power of 2 (i. e. some integer x exists so that ai + aj = 2x).

Input

The first line contains the single positive integer n (1 ≤ n ≤ 105) — the number of integers.

The second line contains n positive integers a1, a2, ..., an (1 ≤ ai ≤ 109).

Output

Print the number of pairs of indexes i, j (i < j) that ai + aj is a power of 2.

Examples

input

47 3 2 1

output

input

31 1 1

output

3

第一行说明输入多少个数第二行n个数求里面有多少组数的和为2的k次方

#include <bits/stdc++.h>
using namespace std;
#define ll long long
map<int,int>M;

int main()
{
    ll n;
    cin >> n;
    ll ans = 0;
    ll a;
    ll Fuc = 1;
    while(n--)
    {
        cin >> a;
        for(int i = 0; i < 32; i++)
        {
            if (Fuc < a)
            {
                Fuc *= 2;
                continue;
            }
            else
            {
                ans += M[Fuc-a];
                Fuc *= 2;
            }
        }
        Fuc = 1;
        M[a]++;
    }
    cout << ans << endl;
}
//小心超时哦

巴特西

cf 702B

最新文章

热门文章