James' Party Happiness

James has \(n\) friends. He wants to invite some of them (possibly none) to his party. The \(i^{th}\) friend produces \(a_i\) happiness if invited. However, there are exactly \(n\) seats arranged in a row and, due to social distancing, no two adjacent friends can sit next to each other. Note that some friends may not want to attend (\(a_i\) can be negative), so it might be optimal not to invite all of them. Determine the maximum total happiness that can be achieved by choosing an optimal subset of friends.

inputFormat

The first line contains an integer \(n\) denoting the number of friends. The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) representing the happiness values for each friend.

outputFormat

Output a single integer, the maximum total happiness achievable.

sample

4
1 -1 3 -2

4