题目背景

愿你们能够不被此题所迷倒。

题目描述

小 L 一共有 $n$ 瓶饮料需要拿走，第 $i$ 瓶饮料的重量为 $a_i$。小 L 将会分 $x$ 轮拿饮料（$1 \le x \le n$，$x$ 自定）。每一轮拿饮料，她拿走第 $i$ 瓶（此轮第 $1$ 瓶）饮料耗费的精力值为 $a_i$；假设这轮原来已经耗费 $k$ 的精力值，之后再拿走第 $j$（$1 \le j \le n$）瓶饮料，则拿走这瓶饮料将新耗费 $(k \And a_j) + (k \oplus a_j) - k$ 精力值（$\And$ 表示按位与，$\oplus$ 表示按位异或）。每一轮拿的饮料都是位置连续的一段饮料。我们设第 $i$ 轮拿完饮料总共消耗了 $l_i$ 精力值，请你求出 $\sum\limits_{i=1}^xl_i$。

简易题面:

小 L 的面前有 $n$ 瓶饮料，第 $i$ 瓶的重量为 $w_i$。她会分成若干轮把所有饮料全部拿走，第 $p$ 轮中拿走的第 $k$ 瓶（设拿走的第 $k$ 瓶饮料编号为 $d$）会花费体力 $f_{p,k}=\begin{cases}a_d&(k=1)\\(a_d\operatorname{and}\sum\limits_{1\leqslant j<k}f_{p,j})+(a_d\operatorname{xor}\sum\limits_{1\leqslant j<k}f_{p,j})-\sum\limits_{1\leqslant j<k}f_{p,j}&(k\geqslant2)\end{cases}$。若第 $p$ 轮拿走了 $c$ 瓶饮料，则该轮耗费的体力 $s_p=\sum\limits_{k=1}^cf_{p,k}$。若小 L 用了 $m$ 轮把饮料拿完，请问 $\sum\limits_{p=1}^ms_p$ 最小为多少。

输入格式

第一行输入一个数 $n$。

第二行输入 $n$ 个数，第 $i$ 个数表示 $a_i$。

输出格式

共一行，一个数，表示最小的 $\sum^x_{i=1} l_i$。

4
1 3 8 12

15

提示

【样例解释】

1. 拿走第二瓶饮料，新耗费 $3$ 精力值。
2. 拿走第一瓶饮料，新耗费 $(3\And 1)+(3\oplus 1)-3=0$ 精力值，并将这两瓶饮料拿走，结束这轮。
3. 拿走第三瓶饮料，新耗费 $8$ 精力值。
4. 拿走第四瓶饮料，新耗费 $(8\And 12)+(8\oplus 12)-8=4$ 精力值，将这两瓶饮料拿走，结束这轮。

总共耗费 $3+0+8+4=15$ 精力值。

【数据范围】

对于 $100\%$ 的数据：$1\leq n\leq 10^6$，$0\leq \sum^x_{i=1} l_i \leq 2^{63}-1$，$0\leq a_i \leq 2^{63}-1$。