Counting Index Pairs with XOR Constraints

Given a sequence of non-negative integers \(a_1, a_2, \ldots, a_n\), count the number of index pairs \((i, j)\) (with \(1 \le i, j \le n\)) that satisfy the condition

\(a_i \le (a_i \oplus a_j) \le a_j\)

Here, \(\oplus\) denotes the bitwise XOR operation (the same as the ^ operator in C++). Note that when \(i=j\), the expression becomes \(a_i \le 0 \le a_i\), so such a pair is valid only if \(a_i = 0\>.

Observation: It can be proved that if \(a_i > 0\) then the condition \(a_i \le (a_i \oplus a_j) \le a_j\) forces \(a_i \le a_j\>.

inputFormat

The first line contains a single integer \(n\) (the length of the sequence). The second line contains \(n\) non-negative integers \(a_1, a_2, \ldots, a_n\) separated by spaces.

outputFormat

Output a single integer representing the number of index pairs \((i,j)\) (with \(1 \le i,j \le n\)) that satisfy \(a_i \le (a_i \oplus a_j) \le a_j\).

sample

3
1 2 3

1