Maximum Robbed Amount

In this problem, you are given a row of houses, each with some amount of money. A thief wants to rob houses such that he does not rob two consecutive houses to avoid triggering the alarms. Your task is to determine the maximum amount of money that can be robbed.

The recurrence relation used in dynamic programming is given by: [ dp[i] = \max(dp[i-1],; dp[i-2] + a_i),\quad \text{for } i \geq 2 ]

where (a_i) represents the money in the (i^{th}) house. Use this relation to solve the problem and output the maximum amount of money the thief can rob.

inputFormat

The input is read from standard input (stdin) and consists of two lines:

1. The first line contains a single integer (n) ((1 \leq n \leq 10^5)), the number of houses.
2. The second line contains (n) space-separated integers (a_1, a_2, \ldots, a_n) (each (0 \leq a_i \leq 10^4)), representing the amount of money in each house.

outputFormat

Output a single integer which is the maximum amount of money that can be robbed without alerting the police (i.e., without robbing two consecutive houses). The output should be written to standard output (stdout).## sample

4
1 2 3 1

4