该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

A fastidious farmer wants to pick apples from the apple trees in his orchard. His trees are arranged in a circle, so that the first tree is a neighbor of the last one. To keep his orchard beautiful, he cannot pick apples from neighboring trees. You are given the number of apples on each tree. Design an algorithm for the farmer to pick the maximum number of apples, and output this quantity.

Format

Input

An array $A$ of $N$ numbers, where $N$ is the number of apple trees, and $A$ indicates the number of apples on each tree.

Output

The maximum number of apples the farmer can pick which satisfies the above condition.

Constraints

$1\leq N\leq 100$ $0\leq A_{i}\leq 1000$ for $A_{i}\in A$

Samples

[1, 2, 3]

3

[1, 2, 3, 1]

4