House Robber Problem

You are given a row of houses with each house containing a certain amount of gold. Your task is to determine the maximum amount of gold that can be robbed under the constraint that you cannot rob two adjacent houses.

Formally, if there are (N) houses numbered from 1 to (N), and the (i)-th house contains (g_i) gold, then you cannot rob both house (i) and house (i+1) at the same time.

The recurrence relation for this problem is given by:

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

where (dp[i]) denotes the maximum amount of gold that can be robbed from the first (i) houses.

inputFormat

The input is read from standard input (stdin). The first line contains a single integer (N), the number of houses. The second line contains (N) space-separated integers, where the (i)-th integer represents the amount of gold in the (i)-th house. If (N = 0), the second line will be empty.

outputFormat

Output a single integer to standard output (stdout), which is the maximum amount of gold that can be robbed under the given conditions.## sample

4
1 2 3 1

4