Có ~N~ viên gạch vuông bằng nhau xếp sát nhau thành một hàng dài trên mặt phẳng. Trên viên gạch thứ ~i~ có ghi một giá trị ~A_i~. Một robot được đặt ở trên viên gạch thứ ~1~ và robot sẽ nhảy đến viên gạch cuối cùng (viên gạch thứ ~N~).

Robot chỉ nhảy theo chiều tăng chỉ số. Do hạn chế về kỹ thuật và năng lượng, bước nhảy tiếp theo không thể dài hơn bước vừa nhảy ngay trước đó. Cụ thể, nếu robot đang ở viên gạch thứ ~i~ nhảy tới viên gạch thứ ~j~, sau đó từ viên gạch thứ ~j~ nhảy tới viên gạch thứ ~k~ thì phải thỏa:

• ~k - j \leq j - i~.

Yêu cầu: Hãy tìm tổng giá trị lớn nhất trên các viên gạch mà robot nhảy tới (tính cả viên bắt đầu và viên kết thúc).

Input

Vào từ file văn bản ROBOT.INP gồm ~2~ dòng:

• Dòng ~1~: số nguyên dương ~N~ với giới hạn ~1 \leq N \leq 10^4~.
• Dòng ~2~: ~N~ giá trị ~A_1, A_2, \ldots, A_N~ với giới hạn ~-10^9 \leq A_i \leq 10^9~.

Output

Ghi ra file văn bản ROBOT.OUT:

• Tổng giá trị lớn nhất trên các viên gạch mà robot nhảy tới.

Scoring

• Subtask ~1~: ~1 \leq N \leq 20~
• Subtask ~2~: ~20 \leq N \leq 500~
• Subtask ~3~: Không ràng buộc gì thêm

Example input 1

6
1 -1 5 -2 -1 2

Example output 1

7

Note 1

• Một cách nhảy đạt tổng ~7~: robot thăm các viên có giá trị ~1~, ~5~, ~-1~, ~2~ (tổng ~1 + 5 - 1 + 2 = 7~).