D. ICPC
time limit per test
6 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

Mystia's Izakaya has held a new edition of the International Championship of Portion Consumption (ICPC). Although Mystia did not allocate spots for Whitejade House University (WHU) for destroying the venue in the previous year, the university still sent a team to participate, led by Yuyuko.

On a long table, there are $$$n$$$ seats arranged in a row, with the $$$i$$$-th seat from left to right having a dish with a portion size of $$$a_i$$$. Yuyuko starts at the $$$s$$$-th seat, and at the end of each second, she can move to any seat adjacent to her current seat (she can also choose to stay at her current seat). Any dish on a seat she reaches will be consumed by her.

Yuyuko wants to know the maximum total portion size of the dishes she can consume. You need to calculate the maximum total portion size of the dishes Yuyuko can consume if she starts from the $$$s$$$-th seat and moves for $$$t$$$ seconds, for all positive integers $$$s,t$$$ that satisfy $$$1 \le s \le n, 1 \le t \le 2n$$$.

Input

The first line contains one integer $$$n$$$ ($$$1 \le n \le 5000$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$).

Output

Let $$$F_{i,j}$$$ represent the maximum total portion size of the dishes that Yuyuko can consume starting from seat $$$i$$$ and moving for $$$j$$$ seconds. To verify that you have calculated values of all $$$F_{i,j}$$$ for $$$1 \le i \le n, 1 \le j \le 2n$$$, please output an integer $$$\bigoplus\limits_{i=1}^n \left(i + \bigoplus\limits_{j=1}^{2n} j \cdot F_{i,j}\right)$$$.

Here, $$$\bigoplus$$$ denotes the bitwise XOR operation. Specifically, if $$$a \oplus b$$$ represents the bitwise XOR of two non-negative integers $$$a$$$ and $$$b$$$, then $$$\bigoplus\limits_{i=1}^n x_i = x_1 \oplus x_2 \oplus \ldots \oplus x_n$$$ (where $$$x_1, x_2, \ldots, x_n$$$ are non-negative integers).

This output method is only to reduce the amount of program output and is unrelated to the solution of the problem.

Examples
Input
3
1 2 3
Output
61
Input
6
7 2 1 3 0 8
Output
59
Note

In the first example, values of $$$F_{i,j}$$$ are

$$$F=\begin{bmatrix} 3 & 6 & 6 & 6 & 6 & 6 \\ 5 & 5 & 6 & 6 & 6 & 6 \\ 5 & 6 & 6 & 6 & 6 & 6 \\ \end{bmatrix}$$$

In the second example, values of $$$F_{i,j}$$$ are

$$$F=\begin{bmatrix} 9 & 10 & 13 & 13 & 21 & 21 & 21 & 21 & 21 & 21 & 21 & 21 \\ 9 & 9 & 10 & 14 & 14 & 21 & 21 & 21 & 21 & 21 & 21 & 21 \\ 4 & 10 & 12 & 13 & 14 & 14 & 21 & 21 & 21 & 21 & 21 & 21 \\ 4 & 11 & 13 & 13 & 13 & 14 & 21 & 21 & 21 & 21 & 21 & 21 \\ 8 & 8 & 11 & 13 & 14 & 21 & 21 & 21 & 21 & 21 & 21 & 21 \\ 8 & 11 & 12 & 14 & 21 & 21 & 21 & 21 & 21 & 21 & 21 & 21 \\ \end{bmatrix}$$$