Problem D: Find Number Pairs

Problem D: Find Number Pairs

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 1562  Solved: 332
[Submit][Status][Web Board]

Description

Given a nondecreasing sequence \(a\) with \(n\) integer \(a_1, a_2, ..., a_n\).

Please find the number of pairs of indexes \(i ,  j(i < j)\) that \(a_i + a_j\) is a power of \(2\) .

Input

The 1st line is a positive integer \(n(1⩽ n ⩽ 100000)\)

The 2nd line contains \(n\) integers: \(a_1, a_2, ..., a_n \). For each \(a_i (1⩽ a_i ⩽ 10^9)\)

Output

Print the the number of pairs of indexes \(i ,  j(i < j)\) that \(a_i + a_j\) is a power of \(2\).

Sample Input

4
1 2 3 7

Sample Output

2

HINT

The correspond solutions to the sample is :

1 + 3 = 2^2

1 + 7 = 2^3

[Submit][Status]