CodeForces Powers of Two STL-白红宇

CodeForces Powers of Two STL

阅读量：5110 次

发布时间：2019-06-13

本文共 1530 字，大约阅读时间需要 5 分钟。

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

4 7 3 2 1

output

input

3 1 1 1

output

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.

#include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   using namespace std;#define FIN freopen("input.txt","r",stdin);#define INF 0x3f3f3f3f#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1typedef long long LL;int a[100005];int main(){ //FIN int n; LL ans; map
                    
                      m; while(~scanf("%d",&n)) { ans=0; for(int i=1; i<=n; i++) scanf("%d",&a[i]); m.clear(); for(int i=1; i<=n; i++) { for(LL j=1; j<=2e9; j+=j) { ans+=m[j-a[i]]; } m[a[i]]++; } cout<
                     
                      <