题目描述
You are given a sequence of N integer numbers A. Calculate the sum of Ai AND Aj 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, Ai <= 1.
Subtask 2 (39 points): N <= 1000, Ai <= 10^9.
Subtask 3 (21 points): N <= 10^5, Ai <= 1.
Subtask 4 (27 points): N <= 10^5, Ai <= 10^6.
输入格式
见题面
输出格式
见题面
样例输入
5
1 2 3 4 5
样例输出
9