题目描述

在莆田南少林遗址的古老魔法遗迹中，$n$ 块魔法水晶按给定顺序首尾相接，构成了一个环。第 $i$ 块水晶的能量值为 $A_i$。

学者小洲准备启动遗迹核心。正式开始前，他可以任选一块水晶作为起点，并沿着固定方向依次处理所有水晶。

接下来，他需要恰好进行 $n-1$ 次操作。每次操作时，只能从当前序列最前面的两块水晶中选择一块处理：

• 如果处理当前第一块水晶，则遗迹核心吸收它的能量，遗迹核心会增加该水晶的能量值；
• 如果处理当前第二块水晶，则会引发一次能量反冲，遗迹核心会减少该水晶的能量值。

被处理的水晶会立刻消失，其余水晶的相对顺序保持不变。

经过所有 $n-1$ 次操作后，恰好剩下一块未被处理的水晶。

请你帮小洲求出，在可以自由选择起点的前提下，遗迹核心能够获得的最大能量值。

输入格式

第一行一个整数 $n$，表示魔法水晶的数量。

第二行 $n$ 个整数 $A_1, A_2, \dots, A_n$，表示各块魔法水晶的能量值。

输出格式

输出一个整数，表示遗迹核心能够获得的最大能量值。

样例

4
3 2 1 -5

10

样例1解释

• 选择能量值为 $3$ 的水晶作为起点后，展开得到序列 $[3, 2, 1, -5]$
• 先处理第一块水晶 $3$，答案变为 $3$
• 再处理第一块水晶 $2$，答案变为 $5$
• 最后处理第二块水晶 $-5$，答案变为 $5 - (-5) = 10$
• 因此最大能量值为 $10$

数据范围

• 对于 $60\%$ 的数据，$2 \le n \le 5000$
• 对于 $100\%$ 的数据，$2 \le n \le 2 \times 10^5$，$-10^9 \le A_i \le 10^9$