环线

题目描述

小 A 喜欢坐地铁。地铁环线有 n 个车站，依次以 1..n 标号。车站 i (1 ≤ i < n) 的下一个车站是车站 i+1，车站 n 的下一个车站是车站 1。小 A 会从某个车站出发，沿环线到某个车站结束行程，期间不会再经过同一个车站。当经过车站 x 时会获得 a[x] 点快乐值。请你选择出发车站与结束车站，使获得的快乐值总和最大。

输入格式

第一行一个正整数 n；第二行 n 个整数 a[i]。

输出格式

一行，一个整数，表示最大快乐值。

样例

输入：4\n-1 2 3 0\n输出：5

数据范围

对于所有测试点，保证 1 ≤ n ≤ 2×10^5，-10^9 ≤ a[i] ≤ 10^9。