A carousel has n booths arranged in a ring, numbered 0 to n-1. Booth i holds v[i] in takings. Because the booths form a ring, booth i and booth i+1 are adjacent, and booth n-1 and booth 0 are also adjacent. A collector may empty a set of booths but never two adjacent booths (including the wrap-around pair). Emptying no booth is allowed (total 0).
Determine the maximum total takings collectable. When there is a single booth, it has no neighbour and may be emptied.
Input format
Line 1: the integer n.
Line 2: n space-separated non-negative integers v[0] v[1] ... v[n-1].
Output format
A single integer: the maximum total takings with no two chosen booths adjacent around the ring.
Constraints
- 1 <= n <= 18
- 0 <= v[i] <= 1000