题目描述

给定一个长度为 $n$ 的整数数列 $a$，其中 $a_i$ 表示数列中第 $i$ 个元素的值。你需要计算以下表达式的值：

其中，$⨁$ 表示按位异或运算。

请注意，$\sum_{i=1}^{n} \sum_{j=1}^{n}(a_{i} \bigoplus a_{j})$ 实际上是对数列中所有元素两两进行异或运算，并将结果求和。

输入格式

第一行包含一个整数 $n$（$1 \le n\le10^5$），表示数列的长度。

第二行包含 $n$ 个整数 $a_i$（$0 \le a_i\le10^9$），每个整数之间用空格分隔。

输出格式

输出一个整数，表示表达式的计算结果。

样例

3
1 2 3

12

提示

样例1解释

对于给定的示例输入，数组 $a = [1, 2, 3]$。我们需要计算以下表达式的值：

计算过程如下：

因此，输出为 $12$。

数据范围

• 测试点 $1 - 10$ 满足 $1 \le n\le10^3$，$0 \le a_i\le10^6$。
• 测试点 $11 - 20$ 满足 $1 \le n\le10^5$，$0 \le a_i\le10^9$。