House Robber II

You are a professional robber planning to rob houses along a street. However, the houses are arranged in a circular order, meaning the first and the last houses are adjacent.

Given n houses, where each house has a non-negative amount of money, determine the maximum amount of money you can rob tonight without alerting the police. Note that if two adjacent houses are robbed, the police will be alerted.

Consider the dynamic programming recurrence relation for a linear arrangement of houses:

$$dp[i]=\max(dp[i-1],\,dp[i-2]+money[i])$$

Due to the circular arrangement, the first and the last houses cannot both be robbed, so you must consider two cases: either skip the first house or skip the last house.

inputFormat

The input is read from standard input (stdin). The first line contains an integer n representing the number of houses. The second line contains n space-separated integers, where each integer represents the amount of money in a house arranged in a circle.

outputFormat

Output a single integer to standard output (stdout), which is the maximum amount of money that can be robbed without triggering the alarm.## sample

3
2 3 2

3