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.

Source: codeforces | Difficulty: MEDIUM
Tags: Mathematics

Data structures

Implementation

Complete search


Solutions:
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
ans = 0
mp = {}
n = inp()
for i in map(int, input().split()):
	for k in range(32):
		ans += mp.get((1 << k) - i, 0)
	mp[i] = mp.get(i, 0) + 1
print(ans)


n = int(input())
arr = list(map(int, input().split()))
d = {}
ans = 0
for i in arr:
	for j in range(32):
		ans += d.get((1 << j) - i, 0)
	d[i] = d.get(i, 0) + 1
print(ans)


from collections import Counter
input()
s = 0
c = Counter(map(int, input().split()))
for i in c:
	s += sum((c[i] * (c[i] - 1) // 2 if j == 2 * i else c[i] * c[j - i] for j in [2 ** k for k in range(31)]))
	c[i] = 0
print(s)


input()
sequence = list(map(int, input().split()))
sequence.sort()
repeated_numbers = {}
exponent = 1
sum = 0
for number in sequence:
	while 2 ** exponent <= number:
		exponent += 1
	sum += repeated_numbers.get(2 ** exponent - number, 0)
	repeated_numbers[number] = repeated_numbers.get(number, 0) + 1
print(sum)


n = int(input())
a = list(map(int, input().split()))
d = {}
A = 0
for x in a:
	for j in range(32):
		y = 2 ** j - x
		if y in d:
			A += d[y]
	if x not in d:
		d[x] = 1
	else:
		d[x] += 1
print(A)


n = int(input())
import math
a = list(map(int, input().split()))
dic = {}
x = max(a)
maxp = math.ceil(math.log2(x))
ans = 0
for i in a:
	try:
		dic[i] += 1
	except:
		dic[i] = 1
	for j in range(1, maxp + 2):
		y = 2 ** j - i
		if y < 0:
			continue
		elif y == i:
			if y in dic and dic[y] > 1:
				ans += dic[y]
				ans -= 1
		elif y in dic:
			ans += dic[y]
print(ans)


input()
c = {}
s = 0
for i in map(int, input().split()):
	for p in range(32):
		s += c.get((1 << p) - i, 0)
	c[i] = c.get(i, 0) + 1
print(s)


from collections import Counter
n = int(input())
nums = map(int, input().split())
nums = Counter(nums)
powers = [2 ** p for p in range(1, 32)]
pairs = 0
for num in nums:
	for power in powers:
		pos_num = power - num
		if pos_num in nums:
			if pos_num != num:
				pairs += nums[num] * nums[pos_num]
			else:
				pairs += (nums[num] - 1) * nums[pos_num]
print(pairs // 2)


n = int(input())
s = list(map(int, input().split()))
g = {}
ans = 0
for i in s:
	for j in range(33):
		ans += g.get((1 << j) - i, 0)
	g[i] = g.get(i, 0) + 1
print(ans)


from collections import defaultdict
n = int(input())
arr = list(map(int, input().split()))
po = [1]
for i in range(32):
	po.append(po[-1] * 2)
ans = 0
dic = defaultdict(int)
for i in arr:
	for j in po:
		ans += dic[j - i]
	dic[i] += 1
print(ans)


from collections import Counter
import string
import math
import sys
from fractions import Fraction
from itertools import product

def array_int():
	return [int(i) for i in sys.stdin.readline().split()]

def vary(arrber_of_variables):
	if arrber_of_variables == 1:
		return int(sys.stdin.readline())
	if arrber_of_variables >= 2:
		return map(int, sys.stdin.readline().split())

def makedict(var):
	return dict(Counter(var))

def printDivisors(n):
	divisors = []
	i = 1
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				divisors.append(i)
			else:
				divisors.extend((i, n // i))
		i = i + 1
	return divisors

def countTotalBits(num):
	binary = bin(num)[2:]
	return len(binary)

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
mod = 10 ** 9 + 7

def comp(x):
	return x[1]

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			primes.append(p)
primes = []

def lcm(a, b):
	return a * b // math.gcd(a, b)

def primeFactors(n):
	factors = []
	while n % 2 == 0:
		factors.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			factors.append(i)
			n = n // i
	if n > 2:
		factors.append(n)
	return factors
mod = 10 ** 9 + 7
testCases = 1
for _ in range(testCases):
	n = vary(1)
	num = array_int()
	ct = makedict(num)
	powers = [2 ** i for i in range(1, 33)]
	ans = 0
	for i in num:
		for j in powers:
			if i < j:
				if j - i in ct:
					ans += ct[j - i]
					if j - i == i:
						ans -= 1
	print(ans // 2)


n = int(input())
s = 0
a = list(map(int, input().split()))
d = {a[0]: 1}
for i in range(1, n):
	for p in range(32):
		s += d.get((1 << p) - a[i], 0)
	d[a[i]] = d.get(a[i], 0) + 1
print(s)


import sys
n = int(input())
a = list(map(int, input().split()))
a.sort()
two = [2 ** i for i in range(32)]
cnt = 0
m = {}
for i in a:
	for j in two:
		cnt += m.get(j - i, 0)
	m[i] = m.get(i, 0) + 1
print(cnt)


R = lambda : map(int, input().split())
n = int(input())
res = 0
vsts = {}
for num in R():
	res += sum((vsts.get((1 << pwr) - num, 0) for pwr in range(32)))
	vsts[num] = vsts.get(num, 0) + 1
print(res)


input()
import sys
a = list(map(int, sys.stdin.readline().split()))
b = {}
for i in a:
	if i not in b:
		b[i] = 1
	else:
		b[i] += 1
ans = 0
s = 0
for i in set(a):
	for j in range(0, 32):
		y = 2 ** j - i
		if y == i and i in b:
			s += b[i] * (b[i] - 1) // 2
		elif y in b:
			ans += b[i] * b[y]
print(s + ans // 2)


input()
sequence = list(map(int, input().split()))
repeated_even_numbers = {}
repeated_odd_numbers = {}
sum = 0
for number in sequence:
	if number % 2 == 0:
		for index in range(31):
			sum += repeated_even_numbers.get((1 << index) - number, 0)
		repeated_even_numbers[number] = repeated_even_numbers.get(number, 0) + 1
	else:
		for index in range(31):
			sum += repeated_odd_numbers.get((1 << index) - number, 0)
		repeated_odd_numbers[number] = repeated_odd_numbers.get(number, 0) + 1
print(sum)


n = int(input())
l = list(map(int, input().split()))
dic = {}
for i in range(n):
	x = l[i]
	dic[x] = 0
for i in range(n):
	x = l[i]
	dic[x] += 1
s = max(l)
m = 0
num = 0
while 2 ** m <= s:
	m += 1
for i in range(n):
	a = l[i]
	for j in range(1, m + 1):
		b = 2 ** j - a
		if b in dic:
			if b == a:
				num += dic[b] - 1
			else:
				num += dic[b]
num = int(num / 2)
print(num)


import sys, threading
sys.setrecursionlimit(10 ** 6)
scan = lambda : map(int, input().split())
n = int(input())
ans = 0
hash = {}
for i in scan():
	tmp = 1
	while tmp * 2 <= 1000000000000.0:
		tmp *= 2
		ans += hash.get(tmp - i, 0)
	if hash.get(i, 0):
		hash[i] += 1
	else:
		hash[i] = 1
print(ans)


n = int(input())
a = list(map(int, input().split()))
even = {}
odd = {}
for i in range(len(a)):
	if a[i] % 2 == 0:
		if a[i] in even:
			even[a[i]] += 1
		else:
			even[a[i]] = 1
	elif a[i] in odd:
		odd[a[i]] += 1
	else:
		odd[a[i]] = 1
count = 0
count2 = 0
for (keys, values) in even.items():
	for i in range(33):
		p = int(pow(2, i)) - keys
		if p > 0:
			if p in even:
				if keys == p:
					count += values * (values - 1) // 2
				else:
					count2 += values * even[p]
for (keys, values) in odd.items():
	for i in range(33):
		p = int(pow(2, i)) - keys
		if p > 0:
			if p in odd:
				if keys == p:
					count += values * (values - 1) // 2
				else:
					count2 += values * odd[p]
print(count + count2 // 2)


input()
a = list(map(int, input().split()))
count = {}
ret = 0
for num in a:
	for shift in range(32):
		p = 1 << shift
		need = p - num
		if need <= 0:
			continue
		ret += count.get(need, 0)
	count.setdefault(num, 0)
	count[num] += 1
print(ret)


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)


lst = [2 ** i for i in range(1, 34)]
s = dict()
n = int(input())
ss = [int(i) for i in input().split()]
sss = 0
for i in range(0, n):
	for j in lst:
		if j - ss[i] in s:
			sss += s[j - ss[i]]
	if ss[i] in s:
		s[ss[i]] += 1
	else:
		s[ss[i]] = 1
print(sss)


twoPowers = [2 << x for x in range(32)]
numbers = {}
n = input()
for x in [int(x) for x in input().split()]:
	if x not in numbers:
		numbers[x] = 0
	numbers[x] += 1
sum = 0
for twoPower in twoPowers:
	for key in numbers:
		if key <= twoPower >> 1:
			oppositeKey = twoPower - key
			if key == oppositeKey:
				sum += numbers[key] * (numbers[key] - 1) // 2
			elif oppositeKey in numbers:
				sum += numbers[key] * numbers[oppositeKey]
print(sum)


def main():
	from sys import stdin, stdout
	n = int(stdin.readline())
	t = tuple(map(int, stdin.readline().split()))
	dic = {}
	asum = 0
	for i in t:
		for j in range(32):
			x = (1 << j) - i
			if x in dic:
				asum += dic[x]
		if i not in dic:
			dic[i] = 1
		else:
			dic[i] += 1
	stdout.write(str(asum))
main()


from collections import defaultdict

def f(arr, n):
	answer = 0
	pp = [2 ** i for i in range(40)]
	dct = {}
	pref = 0
	for i in range(0, len(arr)):
		for num in pp:
			need = num - arr[i]
			answer += dct.get(need, 0)
		dct[arr[i]] = dct.get(arr[i], 0) + 1
	return answer
a = int(input())
l = list(map(int, input().strip().split()))
print(f(l, a))


def main():
	from collections import Counter
	from bisect import bisect_left
	(n, res) = (int(input()), 0)
	cnt = Counter(map(int, input().split()))
	(aa, bb) = (sorted(cnt.keys()), [])
	b = 2 << aa[-1].bit_length()
	aa.append(b)
	while b > aa[0]:
		bb.append(b)
		b //= 2
	for a in aa:
		for b in bb:
			c = b - a
			if c < a:
				del bb[-1]
				break
			if aa[bisect_left(aa, c)] == c:
				res += cnt[a] * cnt[c] if a < c else cnt[a] * (cnt[a] - 1) // 2
	print(res)
main()


import sys
from math import *
n = int(input())
a = list(map(int, input().split()))
value = {}
res = 0
for x in a:
	for i in range(32):
		if (1 << i) - x in value:
			res += value[(1 << i) - x]
	if x in value:
		value[x] += 1
	else:
		value[x] = 1
print(res)


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


import os
import sys
debug = True
if debug and os.path.exists('input.in'):
	input = open('input.in', 'r').readline
else:
	debug = False
	input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
test_count = 1
if debug:
	test_count = int(input())
for t in range(test_count):
	N = inp()
	A = inlt()
	value_map = {}
	for x in A:
		if x in value_map:
			value_map[x] = value_map[x] + 1
		else:
			value_map[x] = 1
	two_power = []
	curr = 1
	while curr <= 2000000000:
		two_power.append(curr)
		curr *= 2
	total = 0
	for x in value_map.keys():
		x_count = value_map[x]
		for p in two_power:
			if x < p:
				diff = p - x
				if diff >= x and diff in value_map:
					if diff == x:
						total += x_count * (x_count - 1) // 2
					else:
						total += x_count * value_map[diff]
	print(total)


from functools import reduce
import os
import sys
from math import *
from collections import *
from fractions import *
from bisect import *
from heapq import *
from io import BytesIO, IOBase
input = lambda : sys.stdin.readline().rstrip('\r\n')

def value():
	return tuple(map(int, input().split()))

def arr():
	return [int(i) for i in input().split()]

def sarr():
	return [int(i) for i in input()]

def starr():
	return [str(x) for x in input().split()]

def inn():
	return int(input())

def svalue():
	return tuple(map(str, input().split()))

def parr():
	return [value() for i in range(n)]
mo = 1000000007
n = inn()
a = arr()
p2 = []
i = 1
while i < 1000000000000000:
	p2 += [i]
	i *= 2
if len(set(a)) == 1 and len(a) > 2:
	if a[0] + a[1] in p2:
		print(n * (n - 1) // 2)
	else:
		print(0)
	exit()
d = defaultdict(list)
for i in range(n):
	d[a[i]] += [i]
ans = 0
for i in range(n):
	for j in range(len(p2)):
		temp = p2[j] - a[i]
		if temp in d:
			res = bisect_left(d[temp], i)
			ans += res
print(ans)


n = int(input())
d = {}
for i in input().split():
	if int(i) in d:
		d[int(i)] += 1
	else:
		d[int(i)] = 1
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:
				ans += d[j - i] * d[i]
			else:
				ans += (d[i] - 1) * d[i]
print(ans // 2)


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().strip())
a = list(map(int, input().strip().split()))
res = 0
countVal = {}
for i in range(n):
	pow2 = 1
	for j in range(30):
		pow2 *= 2
		if pow2 > a[i]:
			remain = pow2 - a[i]
			if remain in countVal:
				res += countVal[remain]
	if a[i] in countVal:
		countVal[a[i]] += 1
	else:
		countVal[a[i]] = 1
print(res)


def main():
	input()
	m = list(map(int, input().split()))
	mp = dict()
	ans = 0
	MX = 1 << 32 + 1
	for x in m:
		cur = 1
		while cur < x:
			cur <<= 1
		while cur < MX:
			if cur - x in mp:
				ans += mp[cur - x]
			cur <<= 1
		if x in mp:
			mp[x] += 1
		else:
			mp[x] = 1
	print(ans)
main()


n = int(input())
array = list(map(int, input().split()))
d = {}
powers = [2 ** i for i in range(1, 32)]
s = 0
for i in range(n):
	e = array[i]
	if i > 0:
		for p in powers:
			if p > e:
				s += d.get(p - e, 0)
	if e not in d:
		d[e] = 0
	d[e] += 1
print(s)


n = int(input())
numbers = list(map(int, input().split()))
sced = set(numbers)
counter = {}
for k in numbers:
	if k in counter:
		counter[k] += 1
	else:
		counter[k] = 1
x = 1
ans = 0
for i in range(32):
	for j in sced:
		if j <= x:
			if j == x:
				ans += counter[x] * (counter[x] - 1) // 2
			elif x * 2 - j in counter:
				ans += counter[j] * counter[x * 2 - j]
	x *= 2
print(ans)


n = int(input())
d = dict()
for i in input().split():
	if int(i) in d:
		d[int(i)] += 1
	else:
		d[int(i)] = 1
mylist = []
ans = 0
for a in range(1, 31):
	mylist.append(2 ** a)
for a in d:
	for b in mylist:
		if b - a in d:
			if b - a != a:
				ans += d[b - a] * d[a]
			else:
				ans += (d[a] - 1) * d[a]
print(ans // 2)


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


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import Counter
n = int(input())
arr = list(map(int, input().split()))
cnt = Counter()
ans = 0
for v in arr:
	for i in range(32):
		ans += cnt[2 ** i - v]
	cnt[v] += 1
print(ans)


n = int(input())
a = list(map(int, input().split()))
pow2 = [2 ** i for i in range(61)]
d = {}
num = 0
for i in range(n):
	for k in range(60):
		if pow2[k] - a[i] in d:
			num += d[pow2[k] - a[i]]
	if a[i] in d:
		d[a[i]] += 1
	else:
		d[a[i]] = 1
print(num)


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest
sys.setrecursionlimit(111111)
INF = 99999999999999999999999999999999

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

def main():
	mod = 1000000007
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = 1
	z = [1]
	for i in range(35):
		z.append(z[-1] * 2)
	for _ in range(tc):
		n = ri()
		a = ria()
		d = Counter(a)
		count = 0
		for i in a:
			for j in z:
				if j - i in d:
					if j == 2 * i:
						count += d[i] - 1
					else:
						count += d[j - i]
			d[i] -= 1
		wi(count)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


n = int(input())
ar = list(map(int, input().split()))
d = {}
for i in ar:
	if i not in d:
		d[i] = 1
	else:
		d[i] = d[i] + 1
ans = 0
for p in d:
	for j in range(31):
		x = 1 << j
		if x == 2 * p:
			ans += d[p] * (d[p] - 1)
		elif x - p in d:
			ans += d[p] * d[x - p]
print(ans // 2)


n = input()
count = {}
ret = 0
for i in map(int, input().split()):
	for val in range(32):
		ret += count.get((1 << val) - i, 0)
	count[i] = count.get(i, 0) + 1
print(ret)


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())
cnt = dict()
res = 0
for x in input().split():
	x = int(x)
	for pw in [2 ** j for j in range(32)]:
		if pw - x in cnt:
			res += cnt[pw - x]
	if x in cnt:
		cnt[x] += 1
	else:
		cnt[x] = 1
print(res)


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 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 math
n = int(input())
a = list(map(int, input().split()))
l = [int(math.pow(2, i)) for i in range(1, 32)]
s = dict()
for i in a:
	if i in s.keys():
		s[i] += 1
	else:
		s[i] = 1
c = 0
for k in s.keys():
	for j in l:
		if j - k in s.keys():
			if j - k == k:
				c += s[k] * (s[j - k] - 1)
			else:
				c += s[k] * s[j - k]
print(c // 2)


import sys
input = sys.stdin.readline
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
p = [2]
while p[-1] * 2 <= 10 ** 18:
	p.append(p[-1] * 2)
cnt = Counter(a)
ans = 0
for (k, v) in cnt.items():
	for pi in p:
		k2 = pi - k
		if k == k2:
			ans += cnt[k] * (cnt[k] - 1)
		else:
			ans += cnt[k] * cnt[k2]
print(ans // 2)


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)


from collections import Counter
n = int(input())
arr = list(map(int, input().split()))
cnt = Counter()
ans = 0
for v in arr:
	for i in range(32):
		ans += cnt[2 ** i - v]
	cnt[v] += 1
print(ans)


import collections
input()
C = collections.Counter(map(int, input().split()))
s = 0
for (x, w) in C.items():
	y = (1 << x.bit_length()) - x
	s += w * C[y] if x > y else w * (w - 1) >> 1
print(s)


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 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)


from fractions import gcd
from datetime import date
from math import factorial
import functools
from heapq import *
from collections import deque
import collections
import math
from collections import defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
inf = float('inf')

def main():
	n = int(input())
	a = list(map(int, input().split()))
	d = Counter(a)
	ans = 0
	for k in a:
		d[k] -= 1
		for i in range(32):
			if 2 ** i - k < 0:
				continue
			if d[2 ** i - k] > 0:
				ans += d[2 ** i - k]
	print(ans)
main()


t = input
p = print
r = range
n = int(t())
a = list(map(int, t().split()))
c = 0
co = {x: 0 for x in range(1000000)}
po = [2 ** x for x in range(33)]
for i in range(n):
	if a[i] in co:
		c += co.get(a[i])
	for j in range(len(po)):
		if a[i] < po[j]:
			co.update({po[j] - a[i]: co.get(po[j] - a[i], 0) + 1})
p(c)


from collections import defaultdict
n = int(input())
lst = list(map(int, input().split()))
dct = defaultdict(int)
ans = 0
for i in lst:
	for j in range(32):
		ans = ans + dct[(1 << j) - i]
	dct[i] += 1
print(ans)


from sys import stdin, stdout

def INI():
	return int(stdin.readline())

def INL():
	return [int(_) for _ in stdin.readline().split()]

def INS():
	return stdin.readline()

def MOD():
	return pow(10, 9) + 7

def OPS(ans):
	stdout.write(str(ans) + '\n')

def OPL(ans):
	[stdout.write(str(_) + ' ') for _ in ans]
	stdout.write('\n')
from math import log2
n = INI()
X = sorted(INL())
D = [1 << _ for _ in range(31)]
ans = 0
M = dict()
for _ in range(n):
	for __ in D:
		if __ - X[_] in M:
			ans += M[__ - X[_]]
	if X[_] in M:
		M[X[_]] += 1
	else:
		M[X[_]] = 1
OPS(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)


freq = {}
n = int(input())
a = [int(x) for x in input().split()]
ans = 0
for x in a:
	for b in range(1, 30 + 1):
		ans += freq.get(2 ** b - x, 0)
	freq[x] = freq.get(x, 0) + 1
print(ans)


from collections import defaultdict
from sys import stdin
inp = stdin.readline
n = int(inp())
a = list(map(int, inp().split()))
freq = defaultdict(int)
ans = 0
for i in range(n):
	freq[a[i]] += 1
for i in range(n):
	freq[a[i]] -= 1
	for j in range(32):
		power_of_2 = 1 << j
		if power_of_2 - a[i] in freq:
			ans += freq[power_of_2 - a[i]]
print(ans)


n = int(input())
val = list(map(int, input().split()))
from collections import Counter
cnt = Counter(val)
powers = [2 ** i for i in range(31)]
ans = 0
for i in cnt.keys():
	for p in range(31):
		temp = powers[p] - i
		if temp > i:
			ans += cnt[i] * cnt.get(temp, 0)
		elif temp == i:
			ans += cnt[i] * (cnt[i] - 1) // 2
print(ans)


import sys, os
from io import BytesIO, IOBase
import collections, itertools, bisect, heapq, math, string
from decimal import *
BUFSIZE = 8192
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def main():
	n = int(input())
	a = list(map(int, input().split()))
	d = collections.Counter(a)
	k = d.keys()
	ans = 0
	for i in range(1, 32):
		t = 2 ** i
		temp = collections.defaultdict()
		for j in k:
			temp[j] = False
		for j in k:
			if not temp[j]:
				if 2 * j == t:
					ans += d[j] * (d[j] - 1) // 2
					temp[j] = True
				elif t - j in k:
					ans += d[j] * d[t - j]
					(temp[j], temp[t - j]) = (True, True)
	print(ans)
main()


from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
mp = defaultdict(int)
for x in a:
	mp[x] += 1
ans = 0
for x in a:
	mp[x] -= 1
	for i in range(1, 31):
		if 2 ** i > x:
			ans += mp[2 ** i - x]
print(ans)


n = int(input())
l = list(map(int, input().split()))
twos = []
twos.append(1)
freq = {}
while twos[-1] < int(1000000000.0):
	twos.append(twos[-1] * 2)
for i in range(n):
	freq[l[i]] = 0
for i in range(n):
	freq[l[i]] += 1
answer = 0
for i in range(0, l.__len__()):
	for j in range(0, twos.__len__()):
		if twos[j] >= l[i] and twos[j] - l[i] in freq and (twos[j] - l[i] != l[i]):
			answer += freq[twos[j] - l[i]]
		elif twos[j] >= l[i] and twos[j] - l[i] in freq and (twos[j] - l[i] == l[i]):
			answer += freq[twos[j] - l[i]] - 1
print(answer // 2)


def s():
	input()
	res = 0
	ss = dict()
	nums = [1]
	while nums[-1] < 10 ** 9:
		nums.append(nums[-1] * 2)
	for i in map(int, input().split()):
		for j in nums:
			if j - i in ss:
				res += ss[j - i]
		if i in ss:
			ss[i] += 1
		else:
			ss[i] = 1
	return res
print(s())


from collections import Counter
p = [2 ** i for i in range(1, 34)]
n = int(input())
l = list(map(int, input().split()))
d = Counter(l)
ans = 0
for i in range(n):
	for j in range(33):
		req = p[j] - l[i]
		if d[req] > 0:
			if req == l[i]:
				ans += d[l[i]] - 1
			else:
				ans += d[req]
print(ans // 2)


n = int(input())
a = [int(x) for x in input().split()]
p2 = [2 ** i for i in range(31)]
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)


from sys import stdin as si
from collections import Counter as c
from math import ceil as ce

class Solution:

	def __init__(self):
		self.td = [1]
		x = 2
		while x < pow(10, 9) * 4:
			self.td.append(x)
			x *= 2

	def bazinga(self, m):
		ans = 0
		md = c(m)
		for k in md:
			for x in self.td:
				if x > k and x - k in md and (x - k != k):
					ans += md[k] * md[x - k]
				if x > k and x - k in md and (x - k == k):
					ans += md[k] * (md[k] - 1)
		print(ce(ans / 2))
n = si.readline().strip()
m = list(map(int, si.readline().strip().split()))
S = Solution()
S.bazinga(m)


n = int(input())
arr = [int(z) for z in input().split()]
arr.sort()
occ = {}
for i in set(arr):
	occ[i] = 0
for i in arr:
	occ[i] += 1
res = 0
for power in range(32):
	for i in arr:
		if not occ.get(2 ** power - i):
			continue
		if 2 ** power - i == i:
			res += occ[i] - 1
		else:
			res += occ[2 ** power - i]
print(res // 2)


n = int(input())
c = list(map(int, input().split()))
p = list()
for i in range(1, int(1000000000.0)):
	if 2 ** i > int(1000000000.0) * 2:
		break
	p.append(2 ** i)
v = dict()
d = dict()
for x in c:
	for y in p:
		if 2 * x == y:
			d[x] = d.get(x, 0) + 1
			continue
		v[y - x] = v.get(y - x, 0) + 1
r = 0
for x in c:
	r += v.get(x, 0)
for x in d.values():
	r += x * (x - 1)
print(r // 2)


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)


import math
n = int(input())
l = list(map(int, input().split()))
p = [2 ** i for i in range(1, 34)]
d = {}
c = 0
for i in range(len(l)):
	for j in p:
		if j - l[i] in d:
			c += d[j - l[i]]
	if l[i] in d:
		d[l[i]] += 1
	else:
		d[l[i]] = 1
print(c)


import sys
import bisect
from bisect import bisect_left as lb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0

def hnbhai(tc):
	n = sb()
	a = sd()
	d = {}
	ans = 0
	for i in range(n):
		for j in range(32):
			if d.get((1 << j) - a[i]):
				ans += d[(1 << j) - a[i]]
		d[a[i]] = d.get(a[i], 0) + 1
	print(ans)
for _ in range(1):
	hnbhai(_ + 1)


input()
d = {}
k = 0
for i in map(int, input().split()):
	for p in range(32):
		k += d.get(2 ** p - i, 0)
	d[i] = d.get(i, 0) + 1
print(k)


def binary(x):
	b_left = -1
	b_right = x - 1
	b_power = power(mas[x])
	while b_right != b_left:
		b_middle = (b_left + b_right + 1) // 2
		if mas[b_middle] + mas[x] >= b_power:
			b_right = b_middle - 1
		else:
			b_left = b_middle
	left_border = b_left
	b_right = x
	b_left = 0
	while b_right != b_left:
		b_middle = (b_left + b_right) // 2
		if mas[b_middle] + mas[x] > b_power:
			b_right = b_middle
		else:
			b_left = b_middle + 1
	right_border = b_right
	return right_border - left_border - 1

def power(x):
	p_answer = 2
	while x != 1:
		x = x // 2
		p_answer = p_answer * 2
	return p_answer
N = int(input())
mas = [int(x) for x in input().split()]
mas.sort()
answer = 0
for i in range(N - 1, 0, -1):
	answer = answer + binary(i)
print(answer)


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)


from collections import Counter
n = int(input())
a = input().split()
a = [int(i) for i in a]
ans = 0
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)


from sys import stdin, stdout
import math
n = int(stdin.readline()[:-1])
a = sorted([int(num) for num in stdin.readline()[:-1].split(' ')])
b = [2 ** (math.floor(math.log(num, 2)) + 1) - num for num in a]
ans = 0
d = {}
da = {num: [0, 0] for num in a}
for i in range(n):
	da[a[i]][0] += 1
	da[a[i]][1] = b[i]
for i in da:
	if i == da[i][1]:
		ans += da[i][0] * (da[i][0] - 1) // 2
	elif da[i][1] in da:
		ans += da[da[i][1]][0] * da[i][0]
stdout.write(str(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)


import sys
from collections import Counter
n = int(input())
a = sorted(map(int, input().split()))
cnt = Counter()
ans = 0
for x in a:
	p = 1 << len(bin(x)) - 2
	ans += cnt[p - x]
	cnt[x] += 1
print(ans)


n = int(input())
ar = list(map(int, input().split()))
ans = 0
s = {}
for x in ar:
	for i in range(1, 32):
		if 2 ** i - x in s:
			ans += s[2 ** i - x]
	s[x] = s.get(x, 0) + 1
print(ans)


n = int(input())
a = list(map(int, input().split()))
dic = {}
t = 0
for i in range(len(a)):
	sh = 0
	while 2 ** sh <= a[i]:
		sh += 1
	sh -= 1
	for j in range(sh, 31):
		t += dic.get(2 ** j - a[i], 0)
	dic[a[i]] = dic.get(a[i], 0) + 1
print(t)


n = int(input())
s = 0
k = 0
a = list(map(int, input().split()))
d = {}
for i in a:
	if i in d:
		d[i] += 1
	else:
		d[i] = 1
for i in set(a):
	for j in range(32):
		if 1 << j == 2 * i and i in d:
			s += d[i] * (d[i] - 1) // 2
		elif (1 << j) - i in d:
			k += d[i] * d[(1 << j) - i]
print(s + k // 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))


from collections import Counter

def main():
	n = int(input())
	a = list(map(int, input().split()))
	c = Counter()
	ans = 0
	for x in a:
		for i in range(1, 33):
			y = 2 ** i
			ans += c[y - x]
		c[x] += 1
	print(ans)
main()


import os, sys
from io import BytesIO, IOBase
from collections import *

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
BUFSIZE = 8192
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
rstr = lambda : input().strip()
rstrs = lambda : [str(x) for x in input().split()]
rstr_2d = lambda n: [rstr() for _ in range(n)]
rint = lambda : int(input())
rints = lambda : [int(x) for x in input().split()]
rint_2d = lambda n: [rint() for _ in range(n)]
rints_2d = lambda n: [rints() for _ in range(n)]
ceil1 = lambda a, b: (a + b - 1) // b
(n, a) = (rint(), rints())
(mem, po, ans) = (Counter(a), [1 << bit for bit in range(33)], 0)
for i in a:
	for j in po:
		if j >= i:
			diff = j - i
			ans += mem[diff] - (diff == i)
print(ans >> 1)


n = int(input())
a = list(map(int, input().split()))
dp = dict()
ans = 0
for i in range(n):
	pw = 1
	for j in range(32):
		cur1 = a[i]
		cur2 = pw - cur1
		if cur2 in dp:
			ans += dp[cur2]
		pw *= 2
	if a[i] in dp:
		dp[a[i]] += 1
	else:
		dp[a[i]] = 1
print(ans)


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)


pows = []
x = 1
for i in range(32):
	pows.append(x)
	x *= 2

def countPairs(n, d):
	count = 0
	x = 0
	m = 0
	for i in d.keys():
		if i in pows:
			m += d[i]
	while x < 32:
		curr = pows[x]
		for i in d.keys():
			if curr - i in d.keys():
				count += d[i] * d[curr - i]
		x += 1
	count = int((count - m) / 2)
	return count
n = int(input())
d = {}
for i in list(map(int, input().split())):
	if i not in d:
		d[i] = 1
	else:
		d[i] += 1
print(countPairs(n, d))


import math
n = int(input())
N = list(map(int, input().split()))
D = dict()
for i in range(n):
	D[N[i]] = D.get(N[i], 0) + 1
S = {1}
counter = 0
s = 1
for i in range(1, 33):
	s *= 2
	S.add(s)
for elem in D:
	for step in S:
		if D.get(step - elem, 0) > 0:
			if step - elem != elem:
				counter += D[elem] * D[step - elem] / 2
			elif step - elem == elem and D[elem] > 1:
				counter += math.factorial(D[elem]) // (2 * math.factorial(D[elem] - 2))
print(int(counter))


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


input()
ans = 0
s = dict()
for x in map(int, input().split()):
	for i in range(1, 32):
		if (1 << i) - x in s:
			ans += s[(1 << i) - x]
	if x in s:
		s[x] += 1
	else:
		s[x] = 1
print(ans)


n = int(input())
l = list(map(int, input().split()))
twos = set()
for i in range(1, 36):
	twos.add(2 ** i)
dic = {}
for i in range(len(l)):
	if l[i] not in dic:
		dic[l[i]] = 1
	else:
		dic[l[i]] += 1
ans = 0
for i in dic:
	for two in twos:
		x = two - i
		if x > 0:
			if x in dic:
				if x == i:
					ans += dic[i] * (dic[i] - 1)
				else:
					ans += dic[i] * dic[x]
print(int(ans / 2))


n = int(input())
s = list(map(int, input().split()))
g = {}
ans = 0
for i in s:
	for j in range(1, 33):
		check = 1 << j
		if check - i in g:
			ans += g[check - i]
	if i in g:
		g[i] += 1
	else:
		g[i] = 1
print(ans)


import sys
input = sys.stdin.buffer.readline
from collections import Counter

def solution():
	po = [2 ** i for i in range(31)]
	n = int(input())
	l = list(map(int, input().split()))
	c = Counter(l)
	ans = 0
	for i in range(n):
		for j in po:
			x = j - l[i]
			if c.get(x, 0) > 0:
				if x == l[i]:
					ans += c[x] - 1
				else:
					ans += c[x]
	print(ans // 2)
solution()


def main():
	n = int(input())
	l = list(map(int, input().split()))
	cnt = {}
	res = 0
	for x in l:
		for i in range(1, 32):
			power = 1 << i
			if power - x in cnt:
				res += cnt[power - x]
		try:
			cnt[x] += 1
		except KeyError:
			cnt[x] = 1
	print(res)
main()


n = int(input())
a = list(map(int, input().split()))
M = dict()
res = 0
for i in range(n):
	for j in range(31):
		res += M.get(2 ** j - a[i], 0)
	M[a[i]] = M.get(a[i], 0) + 1
print(res)


from collections import Counter
input()
c = Counter()
ans = 0
for x in map(int, input().split()):
	for i in range(1, 31):
		ans += c.get((1 << i) - x, 0)
	c[x] += 1
print(ans)


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)


import math
n = int(input())
l = list(map(int, input().split()))
cnt = 0
a = {}
for i in range(n - 1, -1, -1):
	p = int(math.log(l[i], 2)) + 1
	for m in range(p, 32):
		k = 2 ** m - l[i]
		if k in a:
			cnt += a[k]
	if l[i] in a:
		a[l[i]] += 1
	else:
		a[l[i]] = 1
print(cnt)


n = int(input())
m = {}
for x in list(map(int, input().split())):
	if x in m:
		m[x] += 1
	else:
		m[x] = 1
ans = 0
for x in range(0, 31):
	p2 = 2 ** x
	for i in m.keys():
		if p2 - i in m:
			if p2 - i == i:
				ans += m[i] * (m[i] - 1)
			else:
				ans += m[i] * m[p2 - i]
print(ans // 2)


n = int(input())
array = [int(i) for i in input().split()]
ans = 0
for j in range(32):
	num = 2 ** j
	diction = dict()
	for i in array:
		if i in diction:
			ans += diction[i]
		if num - i > 0:
			if num - i in diction:
				diction[num - i] += 1
			else:
				diction[num - i] = 1
print(ans)


import sys
import bisect
input = sys.stdin.readline
count = 0
x = int(input())
y = sorted([int(y) for y in input().split()])
for i in range(1, x):
	L = bisect.bisect_left(y, (1 << len(bin(y[i])) - 2) - y[i], 0, i)
	R = bisect.bisect_right(y, (1 << len(bin(y[i])) - 2) - y[i], 0, i)
	count += R - L
sys.stdout.write(str(count))


n = int(input())
arr = input().split()
arr = [int(i) for i in arr]
d = {}
for a in arr:
	if a in d:
		d[a] += 1
	else:
		d[a] = 1
count = 0
for a in arr:
	d[a] -= 1
	for n in range(1, 32):
		cp = 2 ** n
		if cp <= a:
			continue
		if cp - a in d:
			count += d[cp - a]
print(count)


import re
import sys
exit = sys.exit
from bisect import bisect_left as bsl, bisect_right as bsr
from collections import Counter, defaultdict as ddict, deque
from functools import lru_cache
cache = lru_cache(None)
from heapq import *
from itertools import *
from math import inf
from pprint import pprint as pp
enum = enumerate
ri = lambda : int(rln())
ris = lambda : list(map(int, rfs()))
rln = sys.stdin.readline
rl = lambda : rln().rstrip('\n')
rfs = lambda : rln().split()
cat = ''.join
catn = '\n'.join
mod = 1000000007
d4 = [(0, -1), (1, 0), (0, 1), (-1, 0)]
d8 = [(-1, -1), (0, -1), (1, -1), (-1, 0), (1, 0), (-1, 1), (0, 1), (1, 1)]
n = ri()
a = ris()
ans = 0
d = ddict(int)
for x in a:
	for i in range(32):
		ans += d[(1 << i) - x]
	d[x] += 1
print(ans)


import bisect
import collections
n = int(input())
nums = list(map(int, input().split()))
count = 0
powerTwo = [2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648]
l = collections.Counter(nums)
for i in range(n):
	w = powerTwo[bisect.bisect_right(powerTwo, nums[i])] - nums[i]
	if nums[i] == w:
		count += (l[w] - 1) / 2
	else:
		count += l[w]
print(int(count))


input()
c = {}
ans = 0
for a in map(int, input().split()):
	for p in range(32):
		ans += c.get((1 << p) - a, 0)
	c[a] = c.get(a, 0) + 1
print(ans)


import bisect

def main():
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	p = list()
	p.append(2)
	for i in range(1, 32):
		p.append(p[i - 1] * 2)
	res = 0
	for i in range(0, n):
		for j in p:
			x = j - a[i]
			if x <= 0:
				continue
			ai = bisect.bisect_left(a, x, i + 1, n)
			if ai != n:
				if a[ai] == x:
					bi = bisect.bisect_right(a, x, i + 1, n)
					res += bi - ai
	print(res)
main()


import math

def c(n):
	return math.factorial(n) / (math.factorial(n - 2) * 2)
n = int(input())
a = list(map(int, input().split()))
s = set()
ans = 0
for i in range(33):
	s.add(2 ** i)
d = dict()
for i in range(len(a)):
	if a[i] in d:
		d[a[i]] += 1
	else:
		d[a[i]] = 1
for elem1 in d:
	for elem2 in s:
		if d.get(elem2 - elem1, 0) > 0:
			if elem1 != elem2 - elem1:
				ans += d[elem1] * d[elem2 - elem1] / 2
			elif d[elem1] > 1:
				ans += c(d[elem1])
print(int(ans))


n = int(input())
arr = [int(x) for x in input().split()]
arr.sort()
s = sum(arr)
d = {}
ans = 0
for i in arr:
	start = 1
	while start <= s:
		if start - i in d:
			ans += d[start - i]
		start *= 2
	if i in d:
		d[i] += 1
	else:
		d[i] = 1
print(ans)


n = int(input())
a = map(int, input().split())
pow2 = []
x = 1
for i in range(32):
	x <<= 1
	pow2.append(x)
ans = 0
cnt = {}
for x in a:
	for y in pow2:
		need = y - x
		if need in cnt:
			ans += cnt[need]
	cnt[x] = cnt.get(x, 0) + 1
print(ans)


from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
ct = 0
f = defaultdict(int)
for i in a:
	ct += f[i]
	for j in range(1, 31):
		if 2 ** j - 1 > 0:
			f[2 ** j - i] += 1
print(ct)


n = int(input())
dictionary = dict()
for i in input().split():
	if int(i) in dictionary:
		dictionary[int(i)] += 1
	else:
		dictionary[int(i)] = 1
powerslist = []
ans = 0
for i in range(1, 32):
	powerslist.append(2 ** i)
for i in dictionary:
	for j in powerslist:
		if j - i in dictionary:
			if j - i != i:
				ans += dictionary[j - i] * dictionary[i]
			else:
				ans += (dictionary[i] - 1) * dictionary[i]
print(ans // 2)


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)


import io, os
import sys
from atexit import register
from random import randint
DEBUG = False
if not DEBUG:
	input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
sys.stdout = io.BytesIO()
register(lambda : os.write(1, sys.stdout.getvalue()))
tokens = []
tokens_next = 0

def nextStr():
	global tokens, tokens_next
	while tokens_next >= len(tokens):
		tokens = input().split()
		tokens_next = 0
	tokens_next += 1
	if type(tokens[tokens_next - 1]) == str:
		return tokens[tokens_next - 1]
	return tokens[tokens_next - 1].decode()

def nextInt():
	return int(nextStr())

def nextIntArr(n):
	return [nextInt() for i in range(n)]

def print(s, end='\n'):
	sys.stdout.write((str(s) + end).encode())

def isPowerOf2(n):
	while n % 2 == 0:
		n //= 2
	return n == 1

def bruteforce(a):
	res = 0
	for i in range(len(a)):
		for j in range(i + 1, len(a)):
			if isPowerOf2(a[i] + a[j]):
				res += 1
				break
	return res

def genTestCase():
	n = randint(1, 20)
	return [randint(1, 10 ** 9) for _ in range(n)]

def solve(a):
	powers = [2 ** i for i in range(50)]
	res = 0
	seen = {}
	for i in a:
		for p in powers:
			res += seen.get(p - i, 0)
		seen[i] = seen.get(i, 0) + 1
	return res
a = nextIntArr(nextInt())
print(solve(a))


def solution():
	n = int(input())
	a = list(map(int, input().split()))
	pow2 = [2 ** i for i in range(61)]
	total = 0
	dic = {}
	for i in range(n):
		for j in range(60):
			if pow2[j] - a[i] in dic:
				total += dic[pow2[j] - a[i]]
		if a[i] in dic:
			dic[a[i]] += 1
		else:
			dic[a[i]] = 1
	print(total)
solution()


input()
arr = list(map(int, input().split()))

def sumK(arr, k):
	m = {}
	total = 0
	for number in arr:
		if number in m:
			total += m[number]
		compl = k - number
		m[compl] = m.get(compl, 0) + 1
	return total
k = 1
ans = 0
while k <= 2 * 10 ** 9:
	ans += sumK(arr, k)
	k *= 2
print(ans)


n = int(input())
ai = list(map(int, input().split()))
nums = {}
ans = 0
for i in range(n):
	num = ai[i]
	length = len(bin(num)[2:])
	for j in range(length, 31):
		num2 = 2 ** j - num
		num4 = 0
		try:
			num4 = nums[num2]
		except:
			num4 = 0
		ans += num4
	try:
		nums[ai[i]] += 1
	except:
		nums[ai[i]] = 1
print(ans)


n = int(input())
a = [int(i) for i in map(int, input().split())]
power = [1]
while power[-1] < 2 * 1000000000.0 + 1:
	power.append(power[-1] * 2)
numbers = {str(i): 0 for i in set(a)}
for i in a:
	numbers[str(i)] += 1
ans = 0
for i in a:
	number = numbers[str(i)]
	if numbers[str(i)] == 0:
		continue
	numbers[str(i)] = 0
	for j in power:
		if j <= i:
			continue
		need = j - i
		if str(need) in numbers:
			if i != need:
				ans += numbers[str(need)] * number
			else:
				ans += number * (number - 1) // 2
print(ans)


n = int(input())
a = [int(x) for x in input().split()]
cnt = 0
D = {}
MAX = max(a)
for i in range(0, n):
	D[a[i]] = D.get(a[i], 0) + 1
DK = D.keys()
for k in DK:
	e0 = 0
	while 1 << e0 <= k:
		e0 += 1
	for e in range(e0, 32):
		pow2 = 1 << e
		if pow2 - k > MAX:
			break
		nk = D.get(k, 0)
		if k == pow2 - k:
			cnt += nk * (nk - 1)
		else:
			np = D.get(pow2 - k, 0)
			cnt += nk * np
print(cnt // 2)


import math
from collections import defaultdict

def solve():
	n = int(input())
	arr = list(map(int, input().split(' ')))
	freq = defaultdict(int)
	total = 0
	power_of_twos = []
	count = 1
	while 2 ** count <= 2 * 10 ** 9:
		power_of_twos.append(2 ** count)
		count += 1
	for i in arr:
		if i in freq:
			total += freq[i]
		for j in power_of_twos:
			if j - i > 0:
				freq[j - i] += 1
	print(total)
solve()


n = int(input())
arr = [int(x) for x in input().strip().split(' ')]
pws = [2 ** x for x in range(33)]
map = {}
ans = 0
for v in arr:
	for p in pws:
		if p - v in map:
			ans = ans + map[p - v]
	if v in map:
		map[v] = map[v] + 1
	else:
		map[v] = 1
print(ans)


from bisect import bisect_left as bi
n = int(input())
a = list(map(int, input().split()))
a.sort()
cnt = {}
for i in range(n):
	cnt[a[i]] = 0
for i in range(n):
	cnt[a[i]] += 1
b = [2 ** (i + 1) for i in range(31)]
c = 0
for i in range(n):
	for j in range(31):
		d = bi(a, b[j] - a[i])
		if d != n:
			if a[d] == b[j] - a[i]:
				c = c + cnt[a[d]]
				if a[d] == a[i]:
					c = c - 1
print(c // 2)


from collections import Counter as c
n = int(input())
l = list(map(int, input().split()))
powers = [2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648]
ans = 0
lis = c(l)
for i in l:
	for p in powers:
		if i >= p:
			continue
		elif i == p // 2:
			ans += lis[i] - 1
		elif p - i in lis:
			ans += lis[p - i]
print(ans // 2)


from math import log
from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
a.sort()
dic = defaultdict(lambda : 0)
ans = 0
for el in a:
	i = int(log(el * 2, 2))
	temp = 2 ** i
	while temp > 0:
		if dic[temp - el] != 0:
			ans += dic[temp - el]
		temp //= 2
	dic[el] += 1
print(ans)


ll = lambda : map(int, input().split())
t = lambda : int(input())
ss = lambda : input()
lx = lambda x: map(int, input().split(x))
from math import log10, log2, ceil, factorial as fac, gcd

def f():
	n = t()
	a = list(ll())
	d = {}
	for i in a:
		if i not in d:
			d[i] = 0
		d[i] += 1
	x = 31
	c = 0
	l = {}
	for i in d.keys():
		k = 0
		while k <= 31:
			try:
				if 2 ** k - i == i:
					c += d[i] * (d[i] - 1) // 2
				else:
					c += d[i] * d[2 ** k - i]
			except:
				pass
			k += 1
		d[i] = 0
	print(c)
f()


import collections as cc
import bisect as bi
I = lambda : list(map(int, input().split()))
(n,) = I()
ar = I()
mapping = cc.defaultdict(int)
ans = 0
for i in range(len(ar)):
	for j in range(32):
		target = pow(2, j)
		curr = target - ar[i]
		if curr in mapping:
			ans += mapping[curr]
	mapping[ar[i]] += 1
print(ans)


def powers_of_two(n, a):
	c = {}
	s = 0
	for x in a:
		for p in range(32):
			s += c.get((1 << p) - x, 0)
		c[x] = c.get(x, 0) + 1
	return s
n = int(input())
a = map(int, input().split())
print(powers_of_two(n, a))


n = int(input())
a = list(map(int, input().split()))
b = dict()
ans = 0
for i in range(n):
	x = 1
	for k in range(0, 31):
		if x > a[i]:
			ans += b.get(x - a[i], 0)
		x *= 2
	b[a[i]] = b.get(a[i], 0) + 1
print(ans)


from collections import Counter, defaultdict, deque
from operator import itemgetter
import math
import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	arr = [int(x) for x in input().split()]
	d = defaultdict(int)
	res = 0
	for el in arr:
		for p in range(32):
			res += d[(1 << p) - el]
		d[el] += 1
	print(res)
tt = 1
for test in range(tt):
	solve()


a = int(input())
from bisect import *
z = list(map(int, input().split()))
from collections import *
al = defaultdict(list)
for i in range(len(z)):
	al[z[i]].append(i)
cnt = 0
for i in range(len(z)):
	for j in range(31):
		r = bisect_right(al[pow(2, j) - z[i]], i)
		cnt += len(al[pow(2, j) - z[i]]) - r
print(cnt)


n = int(input())
numbers = list(map(int, input().split()))
count = 0
power_of_two = {2 ** x for x in range(32)}
count_number = dict()
for number in numbers:
	for s in power_of_two:
		this_freq = count_number.get(s - number, 0)
		count += this_freq
	count_number[number] = count_number.get(number, 0) + 1
print(count)


n = int(input())
a = sorted([int(i) for i in input().split()])
d = {}
for i in range(n):
	if a[i] in d:
		d[a[i]] += 1
	else:
		d[a[i]] = 1
ans = 0
for i in range(32):
	t = 2 ** i
	for j in d:
		if t - j in d:
			if j == t - j:
				ans += (d[j] - 1) * d[j]
			else:
				ans += d[j] * d[t - j]
print(ans // 2)


from math import ceil
from math import floor
from math import sqrt
from math import log
prime = pow(10, 9) + 7

def mod_expo(n, p, m):
	result = 1
	while p != 0:
		if p % 2 == 1:
			result = result * n % m
		p //= 2
		n = n * n % m
	return result

def get_count_pairs(n, X, arr):
	count = 0
	mp = {}
	for i in range(n):
		if arr[i] not in mp:
			mp[arr[i]] = 0
		mp[arr[i]] += 1
	if X == 0:
		arr = set(arr)
		arr = list(arr)
		n = len(arr)
	for i in range(n):
		exor = arr[i] ^ X
		if exor in mp:
			if X == 0:
				count += int(mp[exor] * (mp[exor] - 1) / 2)
			else:
				count += mp[exor]
	if X > 0:
		count //= 2
	return count

def check(n, k):
	v = 0
	left = n
	while left > 0:
		current = min(left, k)
		v += current
		left -= current
		left -= left // 10
	return 2 * v >= n

def get_pair_count(n, arr):
	count = 0
	mp = {}
	for i in range(n):
		if arr[i] not in mp:
			mp[arr[i]] = 0
		mp[arr[i]] += 1
	for i in range(n):
		for deg in range(1, 31):
			val = pow(2, deg) - arr[i]
			if val in mp:
				count += mp[val]
				if val == arr[i]:
					count -= 1
		mp[arr[i]] -= 1
	return count

def find_bsearch(n):
	left = 1
	right = n
	middle = 0
	if n <= 2:
		return 1
	while left < right:
		middle = left + (right - left) // 2
		if check(n, middle):
			if middle == left or not check(n, middle - 1):
				return middle
			right = middle - 1
		else:
			left = middle + 1
	return left

def find_divisors(x):
	divisors = []
	for i in range(2, int(sqrt(x)) + 1):
		if x % i == 0:
			if x == i * i:
				divisors.append(i)
			else:
				divisors.append(i)
				divisors.append(int(x / i))
	return divisors

def find_min(N, d):
	N = str(N)
	d = str(d)
	for i in range(len(N) - 1, -1):
		print(N[i])
		if int(N[i]) > int(d):
			N = ''.join([N[j] for j in range(len(N)) and j != i])
			N += d
	return N
t = 1
while t:
	t = t - 1
	count = 0
	n = int(input())
	arr = list(map(int, input().strip().split()))[:n]
	print(get_pair_count(n, arr))


import sys
input = sys.stdin.readline
print = sys.stdout.write
n = int(input())
ar = list(map(int, input().split()))
p2 = [2 ** i for i in range(1, 64)]
d = dict()
for x in ar:
	try:
		d[x] += 1
	except:
		d[x] = 1
ans = 0
for x in p2:
	for el in set(ar):
		if el * 2 != x:
			try:
				ans += d[el] * d[x - el]
			except:
				pass
		else:
			ans += d[el] * (d[el] - 1)
print(str(int(ans) // 2))


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import collections as col
import math

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 10 ** 9 + 7

def solve():
	N = getInt()
	A = getInts()
	two_pows = []
	curr = 1
	counts = col.defaultdict(int)
	for a in A:
		counts[a] += 1
	while curr < 10 ** 9 + 1:
		curr *= 2
		two_pows.append(curr)
	ans = 0
	for (key, val) in counts.items():
		if 2 * key in two_pows:
			ans += val * (val - 1) // 2
		for tp in two_pows:
			if tp - key > key and tp - key in counts:
				ans += val * counts[tp - key]
	return ans
print(solve())


n = int(input())
a = [int(x) for x in input().split()]
st2 = [1]
while st2[-1] <= 10 ** 10:
	st2.append(st2[-1] * 2)
r = 0
d = {}
for i in range(n):
	for s2 in st2:
		if s2 - a[i] in d:
			r += d[s2 - a[i]]
	d[a[i]] = d.get(a[i], 0) + 1
print(r)


import sys
from bisect import bisect_right as rb
from collections import deque
from queue import PriorityQueue
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
inv = lambda x: pow(x, mod - 2, mod)
mod = 10 ** 9 + 7
for _ in range(1):
	n = ii()
	a = il()
	b = []
	j = 1
	for i in range(32):
		b.append(j)
		j *= 2
	d = {}
	ans = 0
	for i in range(n - 1, -1, -1):
		x = a[i]
		for i in range(32):
			y = b[i] - x
			if d.get(y):
				ans += d[y]
		d[x] = d.get(x, 0) + 1
	print(ans)


import sys
import os.path
import math
import heapq
import copy
from sys import stdin, stdout
from collections import *
from math import gcd, ceil, floor
mod = int(1000000000.0 + 7)
if os.path.exists('Updated prg/Input3d.txt'):
	sys.stdout = open('Updated prg/Output3d.txt', 'w')
	sys.stdin = open('Updated prg/Input3d.txt', 'r')

def sinp():
	return input()

def ninp():
	return int(sinp())

def mapinp():
	return map(int, sinp().split())

def smapinp():
	return map(str, sinp().split())

def linp():
	return list(mapinp())

def sl():
	return list(sinp().split())

def prnt(a):
	print(a)

def prntl(a):
	print(a, end=' ')

def prntlist(l1):
	print(*l1)

def power(n):
	return 1 << n
n = ninp()
a = linp()
result = 0
d1 = dict()
for i in a:
	for j in range(1, 32):
		a1 = power(j)
		if a1 - i in d1:
			result = result + d1[a1 - i]
	if i in d1:
		d1[i] = d1[i] + 1
	else:
		d1[i] = 1
prnt(result)


n = int(input())
arr = list(map(int, input().split()))
count = 0
maxA = 2 * 10 ** 9
compare = []
x = 2
dic = {}
done = {}
while x < maxA:
	compare.append(x)
	x <<= 1
for i in range(n):
	text = str(arr[i])
	if text in dic:
		dic[text] = dic.get(text) + 1
	else:
		dic[text] = 1
for num in arr:
	textNum = str(num)
	if textNum not in done:
		for v in compare:
			if v > num:
				need = v - num
				textNeed = str(need)
				aStyle = textNum + '-' + textNeed
				bStyle = textNeed + '-' + textNum
				if textNeed in dic and aStyle not in done and (bStyle not in dic):
					if num == need:
						amount = dic.get(textNum)
						count += amount * (amount - 1) // 2
					else:
						count += dic.get(textNum) * dic.get(textNeed)
					done[aStyle] = 1
					done[bStyle] = 1
	done[textNum] = 1
print(count)


n = int(input())
l = list(map(int, input().split()))
d = {}
k = 0
for i in range(n):
	for j in range(1, 32):
		m = 2 ** j
		f = -1
		try:
			d[m - l[i]]
			f = 0
		except KeyError:
			pass
		if f == 0:
			k += d[m - l[i]]
	f = -1
	try:
		d[l[i]]
		f = 0
	except KeyError:
		pass
	if f == 0:
		d[l[i]] += 1
	else:
		d[l[i]] = 1
print(k)


from math import log2, ceil

def powerof2(k):
	if 2 ** ceil(log2(k)) == k:
		return ceil(log2(k) + 1)
	return ceil(log2(k))
n = int(input())
a = list(map(int, input().split()))
d = {}
for i in a:
	try:
		d[i] += 1
	except:
		d[i] = 1
c = 0
y = max(a)
for i in a:
	r = powerof2(i)
	for j in range(r, 33):
		if 2 ** j - i > y:
			break
		if 2 ** j - i == i:
			try:
				if d[i] >= 2:
					c += d[i] - 1
			except:
				pass
		else:
			try:
				if d[2 ** j - i] > 0:
					c += d[2 ** j - i]
			except:
				pass
print(c // 2)


import sys
from os import path
import bisect
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output1.txt', 'w')
from heapq import heappop, heappush, heapify
from math import ceil
from collections import defaultdict
maxi = sys.maxsize
mini = -maxi

def countPairs(a, n):
	mp = defaultdict(int)
	a.sort(reverse=True)
	count = 0
	for i in range(n):
		for j in range(32):
			count += mp[(1 << j) - a[i]]
		mp[a[i]] += 1
	return count
n = int(input())
l = list(map(int, input().split()))
print(countPairs(l, n))


import bisect
import sys
input = sys.stdin.readline
n = int(input())
seq = sorted([int(i) for i in input().split()])
poi = 2
count = 0
for i in range(1, n):
	while poi <= seq[i]:
		poi *= 2
	indL = bisect.bisect_left(seq, poi - seq[i], 0, i)
	indR = bisect.bisect_right(seq, poi - seq[i], 0, i)
	count += indR - indL
print(count)


import sys
import math
import operator as op
from functools import reduce
from bisect import *
from collections import deque

def read_line():
	return sys.stdin.readline()[:-1]

def read_int():
	return int(sys.stdin.readline())

def read_int_line():
	return [int(v) for v in sys.stdin.readline().split()]

def read_float_line():
	return [float(v) for v in sys.stdin.readline().split()]

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer / denom
N = int(1000000.0) + 10
fenwick = [0] * N

def add(i, x, n):
	while i < n:
		fenwick[i] += x
		i = i | i + 1

def fsum(i, n):
	res = 0
	while i >= 0:
		res += fenwick[i]
		i = (i & i + 1) - 1
	return res

def fsum_range(i, j, n):
	return fsum(j, n) - fsum(i - 1, n)

def index(a, x):
	i = bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	return -1

def find_lt(a, x):
	i = bisect_left(a, x)
	if i:
		return i - 1
	return -1

def find_le(a, x):
	i = bisect_right(a, x)
	if i:
		return i - 1
	return -1

def find_gt(a, x):
	i = bisect_right(a, x)
	if i != len(a):
		return i
	return -1

def find_ge(a, x):
	i = bisect_left(a, x)
	if i != len(a):
		return i
	return -1
mod = int(1000000000.0) + 7
mod2 = 998244353
t = 1
for i in range(t):
	n = read_int()
	a = read_int_line()
	d = {}
	d1 = {}
	for i in range(n):
		if a[i] in d:
			d[a[i]].append(i)
			d1[a[i]] += 1
		else:
			d[a[i]] = [i]
			d1[a[i]] = 1
	ans = 0
	for i in d:
		for k in d[i]:
			for j in range(33):
				v = (1 << j) - i
				if v in d:
					ind = find_gt(d[v], k)
					if ind == -1:
						continue
					ans += d1[v] - ind
	print(ans)


def answer(n, A):
	count = 0
	d = {A[0]: 1}
	for i in range(1, n):
		for j in range(1, 32):
			if 2 ** j - A[i] in d:
				count += d[2 ** j - A[i]]
		if A[i] in d:
			d[A[i]] += 1
		else:
			d[A[i]] = 1
	return count
n = int(input())
arr = list(map(int, input().split()))
print(answer(n, arr))


n = int(input())
a = [int(n) for n in input().split()]
count = 0
d = {}
for i in range(0, n):
	for j in range(1, 31):
		if 2 ** j - a[i] in d:
			count += d[2 ** j - a[i]]
	if a[i] in d:
		d[a[i]] += 1
	else:
		d[a[i]] = 1
print(count)


from collections import defaultdict
N = int(input())
A = [int(i) for i in input().split()]
d = {}
d = defaultdict(lambda : 0, d)
power_table = [2 ** i for i in range(31)]
sum_val = 0
for i in A:
	for pow_2 in power_table:
		sum_val += d[pow_2 - i]
	d[i] += 1
print(sum_val)


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)


input()
a = list(map(int, input().split()))
a = sorted(a)
total = 0
d = {}
for i in range(len(a)):
	if a[i] in d.keys():
		d[a[i]] += 1
	else:
		d[a[i]] = 1
values = set([2 ** i for i in range(1, 33)])
for i in range(len(a)):
	for val in values:
		diff = val - a[i]
		if diff in d.keys():
			if diff == a[i]:
				total += d[diff] - 1
			else:
				total += d[diff]
print(total // 2)


n = int(input())
l = [int(i) for i in input().split()]
d = {}
ans = 0
for j in range(n):
	for i in range(40):
		ans += d.get((1 << i) - l[j], 0)
	d[l[j]] = d.get(l[j], 0) + 1
print(ans)


n = int(input())
a = list(map(int, input().split()))
d = dict()
ans = 0
for i in range(n):
	for j in range(1, 32):
		ans += d.get(2 ** j - a[i], 0)
	d[a[i]] = d.get(a[i], 0) + 1
print(ans)


import sys

def main():
	ans = 0
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split(' ')))
	store = {}
	power = {}
	for (k, v) in enumerate(a):
		store[v] = store.get(v, 0) + 1
	power[1] = 2
	for i in range(2, 32):
		power[i] = power[i - 1] * 2
	for (k, v) in enumerate(a):
		store[v] -= 1
		for i in range(1, 32):
			if power[i] > v and power[i] - v in store:
				ans += store[power[i] - v]
	return ans
answer = main()
print(answer)


from collections import Counter
n = int(input())
arr = list(map(int, input().split()))
highest = max(arr)
freqs = Counter(arr)
count = 0
for e in freqs:
	power = 2
	while power <= highest + e:
		comp = power - e
		comp_freq = freqs[comp]
		if comp > e:
			count += freqs[e] * comp_freq
		elif comp == e:
			count += comp_freq * (comp_freq - 1) // 2
		power *= 2
print(count)


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 = list(map(int, input().split()))
dic = {}
for i in a:
	if i in dic:
		dic[i] += 1
	else:
		dic[i] = 1
div = 0
for i in range(n):
	dic[a[i]] -= 1
	for j in range(1, 32):
		if 2 ** j - a[i] in dic:
			div += dic[2 ** j - a[i]]
print(abs(div))