题目描述

现在给你一个长度为n的a数组，你需要计算一下$∑^{n-1}_{i=1}$$∑^{n}_{j=i+1}$$f(i,j)$的值。 其中$f(i,j)=ai$^$aj$，^为按位异或运算在c或c++中直接用^即可 题目也就是把数组中所有的任意两个数组拿出来将他们异或运算，且把所有结果相加起来，lzh给奈彼出了这么一道题，奈彼这一看不是非常简单？刷刷写下这一段代码：

int solve(){
  int ans=0,n;
   cin>>n;
    for(int i=1;i<=n;++i){
      for(int j=i+1;j<=n;++j){
         ans+=a[i]^a[j];
   }
}
      return ans;
}

过了一下样例觉得非常对，提交！ 然后喜提了一发超时(tle). 评测机一秒大概能跑$10^{9}$左右 这个程序明显是$o(n^2)$都$10^{10}$了，很明显1s根本解决不了。 作为acm新加入的学弟学妹你能帮帮奈彼学长嘛？

输入

第一行给出一个整数n$(1≤n≤$$10^{5})$代表数组长度. 第二行输入n个数代表$a_1,a_2,a_3......a_n$,表示a数组.($0≤a_i≤1$)

输出

输出$∑^{n-1}_{i=1}$$∑^{n}_{j=i+1}$$f(i,j)$的值

Samples

5
1 0 1 1 1

4