Gottfried 学习了二进制数表示。然后他提出了这个任务并将其呈现给你。
给你一个 $$$n$$$ 非负整数的集合 $$$a_1, \ldots, a_n$$$。您可以执行以下操作:选择两个不同的索引 $$$1 \leq i, j \leq n$$$。如果在运算之前$$$a_i = x$$$,$$$a_j = y$$$,那么在运算之后$$$a_i = x~\mathsf{AND}~y$$$,$$$a_j = x~\mathsf{OR}~y$$$,其中$$$\mathsf{AND}$$$和$$$\mathsf{OR}$$$分别是按位AND和OR (有关正式描述,请参阅注释部分)。该操作可以执行任意次数(可能为零)。
完成所有操作后,计算 $$$\sum_{i=1}^n a_i^2$$$ — 所有 $$$a_i$$$ 的平方和。你能达到的最大平方和是多少?
输入
第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, \ldots, a_n$$$ ($$$0 \leq a_i < 2^{20}$$$)。
输出
打印单个整数 - 经过多次(可能为零)运算后可以获得的最大可能平方和。
示例
输入 #1
1 123
输出 #1
15129
输入 #2
3 1 3 5
输出 #2
51
输入 #3
2 349525 699050
输出 #3
1099509530625
注意
在第一个示例中无法进行任何操作,因此答案是 $$$123^2$$$。
在第二个示例中,我们可以获得集合$$$1, 1, 7$$$,以及$$$1^2 + 1^2 + 7^2 = 51$$$。
如果 $$$x$$$ 和 $$$y$$$ 以具有相同位数(可能带有前导零)的二进制表示,则当且仅当 $$$x$$$ 和 $$$y$$$ 的相应位都设置为 $$$1$$$ 时,$$$x~\mathsf{AND}~y$$$ 的每一位都设置为 $$$1$$$。类似地,当且仅当 $$$x$$$ 和 $$$y$$$ 的相应位中的至少一个设置为 $$$1$$$ 时,$$$x~\mathsf{OR}~y$$$ 的每一位设置为 $$$1$$$。例如,$$$x = 3$$$ 和 $$$y = 5$$$ 表示为 $$$011_2$$$ 和 $$$101_2$$$(最高位在前)。然后,$$$x~\mathsf{AND}~y = 001_2 = 1$$$,以及$$$x~\mathsf{OR}~y = 111_2 = 7$$$。