Loot on a Ring Road

Difficulty: 1600 3000 ms 128 MB

dp

The same no-two-adjacent looting, but the houses form a circle — the first and last house are adjacent too.

Input: the first line has N; the second line has the N loot values.

Output: the maximum loot on the circular street.

Constraints:

• 1 ≤ N ≤ 10⁵
• 0 ≤ a_i ≤ 10⁴

Sample Tests

4
2 3 2 3

6

1
5

5

Read the Editorial