Circular House Robbery

You are given a circular arrangement of houses. Each house contains a certain amount of money. However, the houses have a security system such that robbing two adjacent houses will trigger an alarm. Note that in a circular configuration, the first and the last house are also adjacent.

Your task is to determine the maximum amount of money you can rob without alerting the police.

Formally, if the houses are represented as an array \(a_0, a_1, \dots, a_{n-1}\), you want to choose a subset of these indices such that no two chosen indices are consecutive (with \(0\) and \(n-1\) considered consecutive) and the sum \(\sum a_i\) is maximized. A common recurrence used for such problems is:

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

inputFormat

The first line of the input contains a single integer \(n\) which represents the number of houses. The second line contains \(n\) space-separated integers; the \(i^{th}\) integer represents the amount of money in the \(i^{th}\) house. If \(n = 0\), there is no second line.

outputFormat

Output a single integer: the maximum amount of money that can be robbed without triggering the alarm.

## sample

3
2 3 2

3

</p>