1250 - 小b和环
描述

小b有一个长度为n的环,每个点上有个数字。( 0<=每个点上的数字<=10000 )

现在请你选出一些点,满足选出的任意两个点在环上不相邻,且选出的点的数字之和最大,你只需输出这个最大值。


输入

第一行输入一个数n,其中0<n≤50000; 第二行输入n个非负整数,第i个数表示环上顺时针第i个点上的数字,以空格隔开。


输出

输出一个数,表示最大值。


样例

输入

4
1 2 3 1

输出

4
标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 3
通过次数 2