Description

有一个闯关节目，共设置了n个关卡，节目组将这些关卡围成一圈，编号分别为1、2、3、...、n，挑战第i个关卡可以获得P_i积分。 节目组对于参赛者有如下要求： 1.从1号关卡开始按照编号依次挑战，对于每一个关卡，都可以选择跳过，一旦选择跳过，本关的积分为0，且不能再挑战该关卡； 2.不能挑战两个相邻的关卡，特别地，n号和1号关卡相邻。 例如：挑战了1号关卡，就不能挑战2号和n号关卡，只能选择跳过；请计算参赛者参加闯关节目能获得的最高积分是多少？

Format

Input

第一行包含一个整数n，表示关卡的数量； 第二行包含n个整数P₁，P₂，。。。，P_n,分别表示编号从1到n挑战每个关卡可以获得的积分，整数之间以一个空格隔开。

Output

一个整数，表示参赛者参加闯关节目能获得的最高积分。

Samples

5
1 2 3 4 5

8

Limitation

数据范围： 测试点1～10:1<=n<=10⁵,1<=P_i<=10₉.