Hái nấm

Trên một bờ ruộng có \(n\) ô đất xếp thành một hàng, ô thứ \(i\) có \(a_i\) cây nấm. Bạn muốn hái nấm ở một số ô, nhưng nếu hái hai ô kề nhau thì nấm sẽ không mọc lại được nữa — vì vậy không được hái hai ô kề nhau.

Hãy tính tổng số nấm lớn nhất có thể hái được.

Input

• Dòng đầu chứa số nguyên \(n\) (\(1 \le n \le 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(0 \le a_i \le 10^9\)).

Output

• In tổng số nấm lớn nhất.

Scoring

• Có \(30\%\) số test với \(n \le 20\).

Sample Input 1

5
2 7 9 3 1

Sample Output 1

12

Sample Input 2

4
5 1 1 5

Sample Output 2

10

Notes

Ví dụ 1: hái các ô 1, 3, 5 được \(2 + 9 + 1 = 12\). Ví dụ 2: hái ô 1 và ô 4 được \(10\).