You are given a sequence of N integer numbers A. Calculate the sum of A_i AND A_j for all the pairs (i, j) where i < j.

The AND operation is the Bitwise AND operation, defined as in here.

Input

The first line of input consists of the integer N. 

The second line contains N integer numbers - the sequence A.

Output

Output the answer to the problem on the first line of the output.

Example

Input:
5
1 2 3 4 5

Output:
9

Scoring

Subtask 1 (13 points): N <= 1000, A_i <= 1. 

Subtask 2 (39 points): N <= 1000, A_i <= 10⁹. 

Subtask 3 (21 points): N <= 10⁵, A_i <= 1. 

Subtask 4 (27 points): N <= 10⁵, A_i <= 10⁶.

A very well designed problem that can be easily tackled with bit logic and hashing.

Let us observe few things,   The and operator results in one only when both the bits are ON. So first step is hashing the 

On bits . i.e finding the number of numbers for which 0th bit is on then 1th bit is On then 2nd bit is on and so On. there can be maximum 30 bits.   

Now for a present number we break it bitwise.  Suppose the ith bit of the number is ON then we first decrease the hash count of that bit and then we add power(2,i)*hash[i] to the result . as power(2,i) is the value in decimal of that bit being on

and hash[i] gives the count of such bits on  the right side.

               *** code goes here******

1. #include<iostream>
2. #include<bits/stdc++.h>
3. using namespace std;
4. int hash[35];
5. long long int ans=0;
6. long long int arr[100010];
7. long long int power(int n ,int k)
8. {
9. if(k==0)
10. return 1;
11. long long int temp=power(n,k/2);
12. if(k%2==0)
13. return temp*temp;
14. else
15. return n*temp*temp;
17. }
18. int main()
19. {
20. int n;
21. cin>>n;
22. // cout<<power(2,5)<<" "<<power(2,10)<<endl;
23. for(int i=0;i<n;i++)
24. {
25. cin>>arr[i];
26. for(int k=0;k<31;k++)
27. {
28. if(arr[i]&1<<k)
29. hash[k]++;
30. }
31. }
32. ans=0;
33. // cout<<"done "<<endl;
34. for(int i=0;i<n;i++)
35. {
36. // cout<<arr[i]<<endl;
37. for(int k=0;k<31;k++)
38. {
39. if(arr[i]& 1<<k)
40. {
41. // cout<<"for k ="<<k<<endl;
42. hash[k]--;
43. ans=ans+power(2,k)*hash[k];
44. }
45. }
46. //cout<<"ans wer is "<<ans<<endl;
47. }
48. cout<<ans<<endl;
49. return 0;
50. }
51. ****** ends here *****