题目描述

小依想要多吃点饭，变得圆一些。

有 $n$ 碗饭，第 $i$ 碗中有 $a _ i$ 单位的饭。每碗饭只能吃一次。

定义 $f _ {i, j}$（$1 \le i \le n$，$1 \le j \le 2n$）表示小依从第 $i$ 碗开始，行动 $j$ 次后吃掉的饭的总量的最大值。小依行动一次可以不动，向左一个或向右一个。小依会吃掉经过的所有饭。起始点那碗饭不需要任何行动就能吃到。

小依想要知道 $f$ 数组的所有值。

输入格式

第一行一个正整数 $n$。

接下来 $n$ 个整数表示 $a$。

输出格式

为了减少输出量，你只需要输出 $\bigoplus\limits _ {i = 1} ^ n(i + \bigoplus\limits _ {j = 1} ^ {2n} j\times f _ {i, j})$ 的值，其中 $\bigoplus$ 为求异或和符号。

样例

样例输入 1

5
4 2 4 1 4

样例输出 1

98

样例输入/输出 2

见下发文件 circle2.in/ans。该样例满足测试点 $3 \sim 4$ 的限制。

样例输入/输出 3

见下发文件 circle3.in/ans。该样例满足测试点 $6$ 的限制。

数据范围与提示

本题共 $10$ 个测试点，每个测试点 $10$ 分。

对于所有数据，$1 \le n \le 5000$，$0 \le a _ i \le 10 ^ 9$。