环线
题目描述
小 A 喜欢坐地铁。地铁环线有 n个车站,依次以 1,2,...,n标号。车站 i( 1≤i<n)的下一个车站是车站i+1 。
特殊地,车站n 的下一个车站是车站1 。
小 A 会从某个车站出发,乘坐地铁环线到某个车站结束行程,这意味着小 A 至少会经过一个车站。小 A 不会经过一个车站多次。当小 A 乘坐地铁环线经过车站 i时,小 A 会获得 ai点快乐值。请你安排小 A 的行程,选择出发车站与结束车站,使得获得的快乐值总和最大。
输入格式
第一行,一个正整数n ,表示车站的数量。
第二行, n个整数a1,a2,...an, ,分别表示经过每个车站时获得的快乐值。
输出格式
一行,一个整数,表示小 A 能获得的最大快乐值。
输入样例 1
输出样例 1
输入样例 2
输出样例 2
数据范围
对于20% 的测试点,保证1≤n≤200 。
对于40 % 的测试点,保证 1≤n≤2000。
对于所有测试点,保证 1≤n≤2*105,-109≤ai≤109 。