Problem Description

James has $n$ friends and wants to invite some of them to his party. Each friend, if invited, contributes a happiness value of $a_i$. Note that some friends may not want to attend, so their $a_i$ values can be negative.

His house has only one row of $n$ seats, and due to social distancing, no two people can sit next to each other. James wants to know the maximum sum of happiness values he can achieve by inviting friends optimally.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers representing $a$.

Output Format

Output a single integer, the maximum sum of happiness values.

Sample Input and Output

Sample Input #1

5
3 2 -1 4 5

Sample Output #1

12

Sample Input #2

1
10

Sample Output #2

10

Sample Input #3

6
1 -3 2 10 -4 9

Sample Output #3

21

Notes

Sample #1 Explanation

James can invite the 1st, 4th, and 5th friends.

Sample #2 Explanation

James can invite the only friend.

Sample #3 Explanation

James can invite the 3rd, 4th, and 6th friends.

Data Range

For $100\%$ of the data, $1 \le n \le 2 \times 10^5$, $-10^9 \le a_i \le 10^9$.

见题面 Input 部分

见题面 Output 部分