Problem Description

总教头面前摆放着 $n$ 块环绕成圆的神秘符文石，编号 $1$ 到 $n$。触摸石头 $i$ 会引导你走向石头 $i+1$，而石头 $n$ 的命运之线则绕回石头 $1$，形成一个永恒的循环。

古老的预言揭示：你必须选择一枚符文石作为起点，沿命运之线前行，触摸一系列连续且不重复的石头，最终在某块石头上停下。此为你的“天命旅程”。

每触摸一块符文石 $i$，你便能汲取 $a_i$ 点“灵魂能量”。预言嘱托你：找到那条能让你灵魂能量最为充盈的“天命旅程”。

Input Format

第一行，一个正整数 $n$，表示神秘符文石的数量。 第二行，$n$ 个整数 $a_i$，分别表示触摸每块符文石时获得的灵魂能量。

Output Format

一行，一个整数，表示英雄能获得的最大灵魂能量。

4
-1 2 3 0

5

5
-3 4 -5 1 3

5

Hint

【数据范围】 对于 $20\%$ 的测试点，保证 $1\leq n\leq 200$。 对于 $40\%$ 的测试点，保证 $1\leq n\leq 2000$。 对于所有测试点，保证 $1\leq n\leq 2\times 10^5$，$-10^9\leq a_i\leq 10^9$。