House Robber II

Given a circular street of houses, each house contains a non-negative integer which represents the amount of money available for robbery. Because the houses are arranged in a circle, the first and the last house are considered adjacent. You must determine the maximum amount of money you can rob without alerting the police by robbing two adjacent houses.

Formally, if the money in the i-th house is denoted by (a_i) and the houses are arranged in a circle, then you cannot rob both (a_1) and (a_n). Your task is to compute the maximum sum of money you can rob under these constraints.

inputFormat

The input consists of two lines. The first line contains an integer (n), representing the number of houses. The second line contains (n) space-separated integers, where the i-th integer represents the amount of money in the i-th house.

outputFormat

Output a single integer representing the maximum amount of money that can be robbed without alerting the police.## sample

1
5

5