House Robber

You are given a row of houses, each containing a certain amount of money. Due to security systems, you cannot rob two adjacent houses. Your task is to determine the maximum amount of money you can rob without alerting the police.

Let \(a_i\) be the amount of money in house \(i\). The recurrence relation for dynamic programming is given by:

\(dp[i] = \max(dp[i-1], dp[i-2] + a_i)\) for \(i \ge 2\) with initial conditions \(dp[0] = a_0\) and \(dp[1] = \max(a_0, a_1)\).

Input and output follow standard input and output conventions.

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer \(n\) representing the number of houses.
• If \(n \gt 0\), the second line contains \(n\) space-separated integers representing the amount of money in each house.
• If \(n = 0\) then there are no further inputs.

outputFormat

Output a single integer to stdout which represents the maximum amount of money that can be robbed without ever robbing two adjacent houses.

## sample

4
1 2 3 1

4

</p>