You are given n integers a_1, a_2, ..., a_{n}. Find the number of pairs of indexes i, j (i < j) that a_{i} + a_{j} is a power of 2 (i. e. some integer x exists so that a_{i} + a_{j} = 2^{x}).


-----Input-----

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

The second line contains n positive integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9).


-----Output-----

Print the number of pairs of indexes i, j (i < j) that a_{i} + a_{j} is a power of 2.


-----Examples-----
Input
4
7 3 2 1

Output
2

Input
3
1 1 1

Output
3



-----Note-----

In the first example the following pairs of indexes include in answer: (1, 4) and (2, 4).

In the second example all pairs of indexes (i, j) (where i < j) include in answer.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
a = [int(i) for i in input().split()]

def isp2(x):
	return (x >= 1) and ((x & (x - 1)) == 0)

p2 = [2 ** i for i in range(33)]

d = {}
for i in a:
	if i in d:
		d[i] += 1
	else:
		d[i] = 1

k = 0
for i in d:
	for p in p2:
		j = p - i
		if j > i:
			break;
		if j in d:
			if i == j:
				k += d[i] * (d[i] - 1) // 2
			else:
				k += d[i] * d[j]

print(k)


#!/usr/bin/env python3

from collections import Counter

n = int(input())
a = Counter([int(x) for x in input().split()])
r = 0
for k, v in a.items():
    u = (1<<(k-1).bit_length()) - k
    if u:
        if u in a:
            r += v * a[u]
    else:
        r += v * (v-1) // 2
print(r) 

N = int(input())
A = [int(i) for i in input().split()]
d = {}
for i in A:
    d[i] = d.setdefault(i, 0) + 1

from math import log
l = int(log(max(A))/log(2)) + 2
ans = 0
for i in range(N):
    for j in range(1, l):
        c = (1 << j) - A[i]
        ans += d.get(c, 0)
        ans -= c == A[i]

print(ans//2)


n=int(input())
a=input().split()
for i in range (n):
    a[i]=int(a[i])
a.sort()
found={}
x=1
out=0
for j in a:
    while 2**x<=j:
        x+=1
    left=2**x-j
    try:
        out+=found[left]
    except:
        pass
    try:
        found[j]+=1
    except:
        found[j]=1
print (out)


n=int(input())

d={}

for i in input().split():
    if int(i) in d:
        d[int(i)]+=1
    else:
        d[int(i)]=1
        
lst=[]       
for i in range(1,31):
    lst.append(2**i)

ans=0   

for i in d:
    for j in lst:
        if j-i in d:
            if j-i!=i:
                ans+=d[j-i]*d[i]
            else:
                ans+=(d[i]-1)*(d[i])
            
print(ans//2)

from sys import stdin, stdout
n = int(stdin.readline())
power = [2 ** i for i in range(31)]
d = {}
ans = 0

for value in map(int, stdin.readline().split()):
    for m in power:
        if m >= value and m - value in d:
            ans += d[m - value]
    if value in d:
        d[value] += 1
    else:
        d[value] = 1

stdout.write(str(ans))

n = int(input())
a = input().split()
a = [int(i) for i in a]
d = dict()
ans = 0
for i in range(len(a)):
    ans += d.get(a[i],0)
    for j in range(1,31):
        val = 2**j - a[i]
        if val > 0:
            if val not in d:
                d[val] = 1
            else:
                d[val] += 1
print(ans)


n = int(input())
a = [int(x) for x in input().split()]

b = {}
for t in a:
    if t in b:
        b[t] += 1
    else:
        b[t] = 1

dva =[]
for i in range(31):
    dva.append(2**i)

m = 0
for d in dva:
    for k in list(b.keys()):
        if (k < d):
            if not k == d // 2:
                if d - k in b:
                    m += b[k] * b[d - k]
            else:
                m += b[k] * (b[k] - 1)
                
print(m // 2)



'''
Created on Jul 29, 2016

@author: Md. Rezwanul Haque
'''
#from pip.util import Inf
#import math
''''
n = int(input())
L = list(map(int,input().split()))
cnt  = 0
for i in range(n):
    for j in range(i,n):
        if i<j and (L[i]+L[j])%2 == 0:
            for k in range(31):
                if pow(2, k) == L[i]+L[j]:
                    cnt+=1
                    #print(i,j)
                    break
            
            #cnt+=1
print(cnt)'''


n = int(input())

d = {}

for i in input().split():
    if int(i) in d:
        d[int(i)]+=1
    else:
        d[int(i)] = 1
        
#print(d)
L = []

for i in range(1,33):
    L.append(2**i)
    
ans = 0

for i in d:
    for j in L:
        if j-i in d:
            if j-i!= i:
                #print(d[j-i],d[i])
                ans+=d[j-i]*d[i]
            else:
                #print(d[i]-1,d[i])
                ans+=(d[i]-1)*(d[i])
#print(ans)
print(ans//2)



n = int(input())
a = input().split()
a = [int(i) for i in a]
d = dict()
ans = 0
for i in range(n):
    ans += d.get(a[i],0)
    for j in range(1,31):
        val = 2**j - a[i]
        if val > 0:
            if val not in d:
                d[val] = 1
            else:
                d[val] += 1
print(ans)


n = int(input())
a = input().split()
a = [int(i) for i in a]
d = dict()
ans = 0
for i in range(n):
    ans += d.get(a[i],0)
    for j in range(1,31):
        val = 2**j - a[i]
        if val > 0:
            if val not in d:
                d[val] = 1
            else:
                d[val] += 1
print(ans)

from collections import Counter

n = int(input())
a = input().split()
a = [int(i) for i in a]
#d = dict()
ans = 0
'''
for i in range(n):
    ans += d.get(a[i],0)
    for j in range(1,31):
        val = 2**j - a[i]
        if val > 0:
            if val not in d:
                d[val] = 1
            else:
                d[val] += 1
print(ans)
'''
d = Counter()
for i in range(n):
    for j in range(1,31):
        val = 2**j - a[i]
        if val > 0:
            if val in d:
                ans += d[val]
    d[a[i]] +=1
print(ans)

import collections

n = int(input())
s = list(map(int, input().split()))
c = collections.Counter()
for i in s:
    c[i] += 1

pow = [2**x for x in range(1,32)]

ans = 0
for i in s:
    for j in pow:
        if i >= j:
            continue
        elif i == j//2:
            ans += c[i]-1
        elif j-i in c:
            ans += c[j-i]

print(ans//2)

from collections import Counter
n, c, v = int(input()), Counter(), 0
for x in map(int, input().split()):
    v += sum(c[2 ** i - x] for i in range(31))
    c[x] += 1
print(v)

n = int(input())
A = list(map(int, input().split()))
cnt = {}

for a in A:
    if a in cnt:
        cnt[a] += 1
    else:
        cnt[a] = 1

c = 0
for a in A:
    if cnt[a] > 0:
        cnt[a] -= 1

    for n in range(1, 32):
        cur = 2**n
        if cur - a in cnt:
            c += cnt[cur - a]

print(c)


n = int(input())
A = list(map(int, input().split()))
cnt = {}

for a in A:
    if a in cnt:
        cnt[a] += 1
    else:
        cnt[a] = 1

c = 0
for a in A:
    cnt[a] -= 1
    for n in range(1, 32):
        cur = 2**n
        if cur <= a:
            continue
        if cur - a in cnt:
            c += cnt[cur - a]

print(c)


n = int(input())
A = list(map(int, input().split()))
cnt = {}

for a in A:
    if a in cnt:
        cnt[a] += 1
    else:
        cnt[a] = 1

c = 0
for a in A:
    cnt[a] -= 1
    for n in range(1, 32):
        if 2**n - a in cnt:
            c += cnt[2**n - a]

print(c)


from collections import Counter
n,c,a=int(input()),Counter(),0
for i in map(int,input().split()):
    a+=sum([c[2**j-i] for j in range(32)])
    c[i]+=1
print(a)


from collections import Counter
n,c,a=int(input()),Counter(),0
for i in map(int,input().split()):
    a+=sum([c[2**j-i] for j in range(32)])
    c[i]+=1
print(a)


import bisect

n=int(input())
V=sorted([int(x) for x in input().split()])
cont=0
pot=2

for i in range(1,n):
	while pot <= V[i]:
		pot*=2
	indL=bisect.bisect_left(V,pot-V[i],0,i)
	indR=bisect.bisect_right(V,pot-V[i],0,i)
	cont+=(indR-indL)
		
print(cont)


n=int(input())
arr=list(map(int,input().split()))
p=[]
cnt=0
i=2
while i<10000000007:
    p.append(i)
    i*=2
d={}
for i in arr:
    if i not in d:
        d[i]=0
    d[i]+=1
cnt=0
for i in arr:
    d[i]-=1
    for j in p:
        v = j-i
        if v in d:
            cnt += d[v]
print(cnt)


from collections import Counter
n = int(input())
k = list(map(int, input().split()))
cnt = Counter(k)
exp = [2 ** i for i in range(32)]
pair = 0
for i in k:
    if cnt[i] > 0:
        cnt[i] -= 1
    for j in exp:
        if j - i in cnt:
            pair += cnt[j - i]
print(pair)


n=int(input().strip())
d={}
for i in input().strip().split():
  x=int(i)
  if x in d:
    d[x]+=1
  else:
    d[x]=1
ans=0
for i in d.keys():
  for j in range(1,31):
    x=2**j-i
    if x<i:
      continue
    elif x==i:
      ans+=(d[i]*(d[i]-1))//2
    elif x>i and x in d:
      ans+=d[i]*d[x]
print(ans)

n = int(input())
a = [int(t) for t in input().split()]
counts = dict()
for num in a:
    counts[num] = counts.setdefault(num, 0) + 1

m = max(counts)
pows = [2]
while pows[-1] < m:
    pows.append(2*pows[-1])
pows.append(2*pows[-1])

total = 0
for a in counts:
    matchesFora = 0
    for p in pows:
        if p - a in counts:
            matchesFora += counts[p - a]
            if p - a == a:
                matchesFora -= 1
    total += matchesFora * counts[a]
total //= 2

print(total)

n = int(input())
a = [int(t) for t in input().split()]
counts = dict()
for num in a:
    counts[num] = counts.setdefault(num, 0) + 1

m = max(counts)
pows = [2]
while pows[-1] < m:
    pows.append(2*pows[-1])
pows.append(2*pows[-1])

# total = 0
# for a in counts:
#     matchesFora = 0
#     for p in pows:
#         if p - a in counts:
#             matchesFora += counts[p - a]
#             if p - a == a:
#                 matchesFora -= 1
#     total += matchesFora * counts[a]
# total //= 2

total = 0
for num in a:
    for p in pows:
        if p - num in counts:
            total += counts[p - num]
            if p - num == num:
                total -= 1
total //= 2

print(total)