Non-Adjacent House Beauty

You are given a list of integers representing the beauty levels of houses arranged in a row. You must choose a subset of these houses to maximize the sum of beauty levels, with the constraint that you cannot choose two adjacent houses.

The problem can be formulated using dynamic programming. Define dp[i] as the maximum beauty sum obtainable from the first i+1 houses. The recurrence is given by:

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

with initial conditions $$dp[0]=beauty_0$$ and $$dp[1]=\max(beauty_0,beauty_1)$$ (when applicable). The task is to compute dp[n-1] where n is the number of houses.

inputFormat

The input is read from standard input. The first line contains a non-negative integer n, the number of houses. If n > 0, the second line contains n space-separated integers representing the beauty levels of the houses.

outputFormat

Output a single integer on standard output which is the maximum total beauty that can be obtained by selecting non-adjacent houses.## sample

5
2 7 9 3 1

12