Halloween sắp đến, trung tâm Fullhouse Dev tổ chức phát quà cho học viên. Có \(N\) gói quà với giá trị khác nhau được xếp liên tiếp thành một hàng, trong đó gói quà thứ \(i\) có giá trị là \(a_i\). Mỗi học viên chỉ được chọn \(2\) gói quà liên tiếp. Hiếu là người may mắn được chọn quà đầu tiên. Các bạn hãy giúp Khánh chọn ra được \(2\) gói quà liên tiếp có tổng giá trị lớn nhất.

INPUT FORMAT

• Dòng đầu tiên chứa số nguyên dương \(N (2 \leq N \leq 10^6)\)
• Dòng 2: gồm n số nguyên dương \(a_i (1 \leq a_i \leq 10^3)\)

OUTPUT FORMAT

là tổng giá trị quà lớn nhất có thể chọn được.

Ví dụ:

Input

5
1 3 5 4 2

Output

9

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House