Circular House Robbery

You are given a list of non-negative integers representing the amount of money in each house arranged in a circle. The houses are arranged such that the first and the last house are neighbors. If you rob two adjacent houses, the alarm will be triggered. Your task is to determine the maximum amount of money you can rob without triggering the alarm.

Note: Since the houses form a circle, the first house and the last house cannot be robbed together.

Example:

Input: 4\n1 2 3 1
Output: 4

The optimal strategy is to rob the second and the third houses (2 + 3 = 5) if they were in a line, but because the houses are in a circle, you must choose either the first three or the last three houses. In the sample above, robbing houses with amounts 1 and 3 yields 4, which is the maximum amount that can be safely robbed in this configuration.

inputFormat

The input is read from stdin and consists of two lines:

1. The first line contains a single integer n representing the number of houses.
2. The second line contains n space-separated non-negative integers, where each integer represents the amount of money in a house.

outputFormat

Output a single integer to stdout which represents the maximum amount of money you can rob without alerting the police.

## sample

1
5

5

</p>