Vì vừa đạt giải cao trong một kì thi nên bạn Quý được ban tổ chức trao thưởng. Thể lệ trao thưởng như sau:

Có N bàn xếp thành một hàng ngang, trên mỗi bàn chứa một món quà. Bạn Quý được chọn bất kì món quà nào, hoặc không chọn, nhưng không được chọn quá 2 món quà liên tiếp. Bạn hãy giúp bạn Quý tính xem có thể chọn lượng quà có giá trị lớn nhất là bao nhiêu.

Dữ liệu:

Dòng đầu ghi một số nguyên N. Dòng thứ hai ghi N số nguyên A1, A2, ..., AN thể hiện giá trị của N món quà. Kết quả:

In ra tổng giá trị các món quà lớn nhất mà bạn Quý có thể chọn. Ví dụ

Sample Input

5

6 9 1 3 5

Sample Output

23

Giới hạn

• 40% số test có 1 ≤ N ≤ 20

• 60% số test còn lại có 1 ≤ N ≤ 10^5