Cho dãy số nguyên dương ~a_1, a_2, ..., a_N~ ~(0 < N \le 10^6,\ 0 < a_i \le 10^6,\ 1 \le i \le N)~.

Yêu cầu

Hãy chọn các phần tử của dãy số ~a_1, a_2, ..., a_N~ sao cho có không quá ~3~ phần tử liên tiếp được chọn, đồng thời, tổng các phần tử đã chọn là lớn nhất.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu tiên gồm số ~N~.
• Dòng thứ hai gồm ~N~ số nguyên dương ~a_1, a_2, ..., a_N~, các số cách nhau bằng dấu cách.

Dữ liệu đầu ra

Gồm một số là tổng các phần tử đã chọn lớn nhất.

Ràng buộc dữ liệu

• Có 40% số test ứng với ~N \le 10^2~;
• Có 40% số test ứng với ~10^2 < N \le 10^4~;
• Có 20% số test ứng với ~10^4 < N \le 10^6~.

Ví dụ

Ví dụ 1

INPUT

5
1 4 5 3 9

OUTPUT

19

Giải thích: Chọn phần tử ~1, 4, 5, 9~. Tổng là ~1 + 4 + 5 + 9 = 19~.