CAU3

Cho mảng \(A\) gồm \(N\) số nguyên dương.

Yêu cầu: Hãy chọn ra một tập các phần tử sao cho không có hai phần tử nào kề nhau và tổng các phần tử được chọn là lớn nhất có thể.

Input

• Dòng \(1\): số nguyên \(N\) (\(1 \le N \le 10^5\)).
• Dòng \(2\): \(N\) số nguyên dương, mỗi số không vượt quá \(10^9\).

Output

Một số nguyên duy nhất là tổng lớn nhất có thể.

Sample Input 1

6
5 1 2 10 6 2

Sample Output 1

17

Notes

Chọn \(5 + 10 + 2 = 17\).