Cho một dãy gồm \(N\) số tự nhiên \(a_1, a_2, a_3...a_n\) \((1 \le N \le 10^6; |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ố đã cho, sao cho không có 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 vào:

• Dòng 1: Một số tự nhiên \(N\)
• Dòng 2: \(N\) số tự nhiên \(a_1, a_2, a_3...a_n\)

Dữ liệu ra:

• Một số nguyên duy nhất là kết quả tổng các phần tử đã chọn là lớn nhất

Ràng buộc:

• Có 40% số test tương ứng 40% số điểm \(0 \le N \le 10^2\)
• Có 40% số test tương ứng 40% số điểm \(10^2 \le N \le 10^3\)
• Có 20% số test tương ứng 20% số điểm \(10^3 \le N \le 10^6\)

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