Question

Circular Donation Booths

A charity fair has N donation booths arranged in a circle. Each booth has some donation value. Volunteers cannot collect from two adjacent booths because nearby counters share the same cash supervisor. Since the first and last booths are also adjacent, choose booths with maximum total donation.

Find the maximum donation that can be collected.

Input

The first line contains an integer KaTeX can only parse string typed expression — the number of booths.

The second line contains KaTeX can only parse string typed expression integers KaTeX can only parse string typed expression — the donation values.

Output

Print a single integer — the maximum donation that can be collected.

Example

Example 1:
Input

5

2 3 2 5 1

Output

Explanation
Choose booths with values KaTeX can only parse string typed expression and KaTeX can only parse string typed expression.

Example 2:
Input

4

10 1 1 10

Output

Explanation
The two KaTeX can only parse string typed expression booths are adjacent in the circle, so they cannot both be chosen.

Online

Explore Newton School

Recent Questions

Most Solved Questions

Least Solved Questions