Maximum Lamp Brightness

You are given n lamps, each with an associated brightness value. Your goal is to maximize the sum of brightness values by turning on a subset of lamps such that no two adjacent lamps are lit. In other words, if the brightness values are given as \(a_1, a_2, \dots, a_n\), you must choose a subset of indices \(I\) such that for any two consecutive indices \(i\) and \(j\) in the original order with \(|i - j| = 1\), at most one is chosen. The maximum brightness is then obtained by evaluating the maximum sum:

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

Note that if all brightness values are negative, the optimal strategy is to turn on no lamp, resulting in a total brightness of 0.

inputFormat

The input is read from standard input and consists of two lines. The first line contains an integer \(n\) representing the number of lamps. The second line contains \(n\) space-separated integers, each representing the brightness value of a lamp. If \(n = 0\), the second line may be omitted.

outputFormat

Output to standard output a single integer denoting the maximum brightness sum achievable under the given constraints.

## sample

4
3 2 5 10

13

</p>