Se consideră un șir a[1], a[2],…, a[n] de numere naturale nenule.

Cerința

Să se determine câte perechi de indici (i, j), 1 ≤ i < j ≤ n, există cu proprietatea că suma a[i] + a[j] este egală cu o putere a lui 2.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi cele n numere naturale nenule, separate prin spații.

Date de ieșire

Programul va afișa pe ecran un singur număr natural reprezentând numărul de perechi de indici distincți (i, j) cu proprietatea că suma a[i] + a[j] este egală cu o putere a lui 2.

Restricții și precizări

• 2 ≤ n ≤ 100 000
• 1 ≤ a[i] ≤ 1 000 000 000, pentru orice i = 1..n
• Numerele care sunt puteri ale lui 2 sunt 1, 2, 4, 8, 16, 32, …

Exemplu

Intrare

4
3 5 3 13

Ieșire

4

Explicație

Cele patru perechi de indici sunt: (1,2), (1,4), (2,3), (3,4).

#include <bits/stdc++.h>

using namespace std;

unsigned int v[32];
unsigned int a[100001];

int BS(unsigned int val, int start, int end)
{
    int l = start, r = end, m;
    int poz = -1;
    while (l <= r)
    {
        m = (l + r) / 2;
        if (a[m]==val)
        {
            poz = m;
            break;
        }
        if (a[m] < val)
        {
            l = m + 1;
        }
        else
            r = m - 1;
    }
    return poz;
}


int main ()
{   
    ios::sync_with_stdio(false);
    int i=0;
    v[0]=1;
    for (i = 1; i <= 31; ++i)
        v[i]=v[i-1]*2;

    int n;
    cin >> n;
    int cnt=0;
    int *item;
    
    for (i = 0 ; i < n ; ++i)
    {
        cin >> a[i];
    }
    sort(a, a+n);
    for (i = 0 ; i < n-1 ; ++i)
    {
        for (int j = 31; j > 0 ; --j)
        {
            if (v[j] <= a[i])
               break;
            unsigned int nr = v[j]-a[i];
            if (i <n-1)
            {
                int poz = BS(nr, i+1, n-1);
                if ( poz != -1 )
                {
                    cnt++;
                    int k = poz-1;
                    while (k > i)
                    {
                        if (a[k] == a[poz])
                            cnt++;
                        if (a[k] < a[poz])
                            break;
                        k--;
                    }
                    k = poz +1;
                    while (k < n)
                    {
                        if (a[k] == a[poz])
                            cnt++;
                        if (a[k] > a[poz])
                            break;
                        k++;
                    }
                }
            }
            
        }
        
    }
    
    cout << cnt;
    return 0;
}