Problem1486--地头蛇PIPI II

1486: 地头蛇PIPI II

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 342  Solved: 90
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI是麓山南路的地头蛇~它以收店家保护费为生~
麓山南路上有n家商店排成首尾相连一个环,PIPI为了不引起公愤,每次收完一家商店后保证不收与该商店相邻的左右两家商店的保护费~
现在告诉你每家商店内有多少现金(PIPI进入一家店就会把现金都拿走!),问你今晚PIPI最多能收到多少保护费?

Input

输入包含多组测试样例。
对于每组测试样例,第一行为一个整数n,1<=n<=100000
第二行为n个整数A1,A2...An,表示每家店内的现金。0<=Ai<=10000

Output

对于每组测试样例,输出一个整数,表示最多能收到的保护费。

Sample Input

5
2 5 4 1 3

Sample Output

8

Source/Category