Each sensor reports a non-negative integer status word. The divergence between two sensors is the Hamming distance of their status words: the number of bit positions at which the two words differ.
Given n status words, compute the sum of divergences over every unordered pair of distinct sensors. That is, sum the Hamming distance of a[i] and a[j] over all pairs i < j.
Input format
Line 1: an integer n.
Line 2: n space-separated non-negative integers, the status words.
Output format
A single integer: the total pairwise Hamming distance.
Constraints
- 1 <= n <= 100000
- 0 <= each value <= 1000000000