House Robber II

You are a professional robber planning to rob houses arranged in a circle. Each house has a certain amount of money stashed, but if two adjacent houses are broken into on the same night, the police will be alerted. Given a circular arrangement of houses, your task is to determine the maximum amount of money you can rob tonight without alerting the police.

More formally, if there are n houses with money values represented by an array \( nums[0 \ldots n-1] \), then you cannot rob two consecutive houses. Since the first and last house are adjacent, you must consider them as neighbors.

The problem can be formulated using the following recurrence for a linear street:

[ \text{rob}(i) = \max(\text{rob}(i-1),, \text{rob}(i-2) + nums[i]) ]

For the circular street, consider two cases:

• Rob houses from index 0 to \(n-2\) (exclude the last house).
• Rob houses from index 1 to \(n-1\) (exclude the first house).

Your goal is to calculate the maximum money that can be robbed.

inputFormat

The input is given via stdin in 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 representing the amount of money in each house.

You may assume \(0 \leq n \leq 10^5\) and each money value is between \(0\) and \(10^4\).

outputFormat

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

## sample

3
2 3 2

3