01字典树模板题。

首先我们来考虑 假设我们有一个数x，计算在字典树内的哪些数是合法的答案。

这里我们先从高位开始匹配，假设我们匹配到第i - 1位且x与当前匹配到的前缀的差异值等于相似值。

那么当x的第i位为1时，我们可以选择当前树上节点的0这个分支，这会让后续选择的差异值始终大于相似值（因为之前是相等的）

当x的第i位为0时，我们可以选0， 此时差异值与相似值还是相等的，我们也可以选1，此时子树内所有的数差异值大于相似值。

题目内容

设 $A$ 和 $B$ 的二进制表示为 $a_n,a_{n−1},⋯,a_1$ 和 $b_n,b_{n−1},⋯,b_1$ ，其中 $a_i,b_i ∈\{0,1\}$ ，

则它们的差异值为 $∑_{i=1}^n (a_i ∧ b_i)2^{i−1}$ ，

相似值为 $∑_{i=1}^n(a_i\ \& \ b_i)2^{i−1}$ , 其中 ∧ 表示异或运算， & 表示与运算。

给定 $n$ 个正整数 $A_1,A_2,⋯,A_n$ ，求满足 $A_i$ 和 $A_j$ 的差异值大于相似值的 $(i,j)$ 对数，其中 $0\le i\lt j\lt n$ 。

输入描述

输入第一行为一个整数 $n$ ，表示数组的大小。

输入第二行为 $n$ 个整数，第 $i$ 个元素为 $A_i$ 。

$1\le n \le 10^5$ ， $1\le A_i \le 2^{30}$

输出描述

输出为一个整数，表示满足差异值大于相似值的对数。

样例

样例一

输入

4
4 3 5 2

输出

4

样例解释

有如下4组数据符合条件: $(1 , 2),(1 , 3),(2 , 4),(3 , 4).$

样例二

输入

5
1 2 3 4 5

输出

8

样例解释

有如下8组数据符合条件: $(1 , 2),(1 , 3),(1 , 4),(1 , 5),(2 , 4),(2 , 5),(3 , 4),(3 , 5).$

样例三

输入

5
16 36 35 40 2

输出

7

样例解释

有如下7组数据符合条件: $(1 , 2),(1 , 3),(1 , 4),(1 , 5),(2 , 5),(3 , 5),(4 , 5).$