题目描述

小蓝有 $n$ 个数 $a_i$，他想知道这 $n$ 个数中的所有数对下标的差值乘上它们的异或之后，得到的结果的和是多少。

也就是说，小蓝想要得到

$$\sum_{i=1}^{n} \sum_{j=i+1}^{n} (a_i \oplus a_j) \times (j - i) $$

的值，其中 $\oplus$ 表示按位异或。

输入格式

输入的第一行包含一个正整数 $n$。

第二行包含 $n$ 个正整数 $a_1, a_2, \cdots, a_n$，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

样例

3
1 2 3

8

4
9 8 7 6

118

数据范围

• 对于 $40\%$ 的评测用例，$n \leq 5000$；
• 对于所有评测用例，$1 \leq n \leq 10^5$，$1 \leq a_i \leq 2^{20}$。