Maximum Robbery without Alerting the Police

You are given a row of n houses, each with a certain amount of money. You need to determine the maximum amount of money you can rob tonight without alerting the police. The condition is that adjacent houses cannot be robbed on the same night.

Formally, let \(a_i\) be the amount of money in the \(i\)-th house. Define a function \(dp[i]\) where

[ dp[i] = \max(dp[i-1],; dp[i-2] + a_i) \quad \text{for} ; i \ge 2, ]

with initial conditions \(dp[0] = a_0\) and \(dp[1] = \max(a_0, a_1)\). Your task is to compute \(dp[n-1]\), the maximal money that can be robbed.

inputFormat

The input is given via standard input (stdin). The first line contains a single integer n representing the number of houses. The second line contains n space-separated integers, where the i-th integer represents the amount of money at the i-th house.

For example:

6
2 7 9 3 1 4

outputFormat

Output a single integer to standard output (stdout) — the maximum amount of money that can be robbed without triggering the alarm.

6
2 7 9 3 1 4

15