Trong cuộc thi THT vừa rồi, Tèo đã đạt được giải khá cao, vượt chỉ tiêu mà Tèo và thầy đội tuyển đặt ra.

Nên thầy quyết định cho Tèo quyền chọn ra một số món quà cho bản thân mình.

Thầy đội tuyển chuẩn bị ~n~ món quà được đánh số từ ~1~ đến ~n~, phần thưởng thứ ~i~ ~(i \le n)~ sẽ có giá trị là ~a_i~.

Vì thầy đội tuyển đâu có ngu mà cho Tèo chọn hết. Nên thầy sẽ đưa ra một luật lệ rằng:

• Tèo không thể chọn quá 2 món quà liên tiếp nhau.

Nhưng Tèo cũng đâu phải dạng tép riu đâu. Vừa tài năng vừa tham lam nên Tèo trong một vài giây tính toán đã biết được tổng ~S~ lớn nhất mà mình có thể nhận được.

Tuy tính toán nhanh là vậy, nhưng Tèo lại không quá tin vào kết quả của mình.

Nên Tèo muốn nhờ bạn viết một chương trình kiểm tra xem tổng ~S~ lớn nhất của dãy ~a_i~ ~(i \le n)~ có thể tạo ra là bao nhiêu. Từ đó cậu có thể so sánh với kết quả của mình.

Lưu ý: ~S~ là tổng giá trị của các mòn quà được chọn.

Yêu Cầu: Tìm tổng ~S~ lớn nhất.

INPUT

• Dòng đầu số nguyên dương ~n~ ~(n \le 10^5)~
• Dòng tiếp theo là dãy nguyên dương ~A~ gồm ~n~ phần tử ~(1 \le A_i \le 10^{6})~

OUTPUT

• Gồm một số nguyên dương là yêu cầu của bài toán

SUBTASKS

• Subtask 1 (20%): ~n \le 20~
• Subtask 2 (50%): ~n \le 10^4~
• Subtask 3 (30%): ~n \le 10^5~

SAMPLE

Input

5
5 4 1 3 4

Output

16

Explanation

Các món quà ta có thể chọn để đạt được Smax là:

S = a[1] + a[2] + a[4] + a[5]
  = 5 + 4 + 3 + 4
  = 16