Một nhà khoa học đang nghiên cứu một dải năng lượng bí ẩn trải dài qua nhiều điểm, mỗi điểm được đánh dấu bằng một giá trị năng lượng ~A_i~ (có thể là dương hoặc âm). Họ muốn chọn một đoạn liên tục trong dải này để thu thập năng lượng tối đa.

Nhà khoa học có một thiết bị thu năng lượng hình chữ nhật với kích thước ~2~ x ~k~ (với ~k ≥ 2~ tùy ý). Thiết bị này có thể thu thập năng lượng từ bất kỳ đoạn nào trên dải, nhưng phải đảm bảo thiết bị nằm hoàn toàn trong phạm vi của dải.

Yêu cầu: Hãy giúp nhà khoa học tìm ra vị trí đặt thiết bị sao cho tổng năng lượng thu được là lớn nhất.

Dữ liệu vào:

• Dòng 1 chứa số nguyên dương ~N~ (~4 ≤ N ≤ 10^6~) - số lượng điểm trên dải năng lượng.
• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2,…, A_N~ (~|A_i| ≤ 10^9~ với ~1 ≤ i ≤ N~) - giá trị năng lượng tại mỗi điểm.

Dữ liệu ra:

• Gồm một số nguyên duy nhất là tổng năng lượng lớn nhất có thể thu được từ một đoạn mà thiết bị có thể bao phủ.

Ví dụ:

Input

6
-4 3 -2 -6 7 2

Output

2

Giải thích:

• Đoạn thu được năng lượng cao nhất

3 -2

7 -6

• Tổng năng lượng thu được từ đoạn này là: 3+ (-2) + 7 + (-6) = 2.

Ràng buộc:

• Subtask 1: Có 30% điểm tương ứng với trường hợp ~4 ≤ N ≤ 300~.
• Subtask 2: Có 30% điểm tương ứng với trường hợp ~300 < N ≤ 5000~.
• Subtask 3: Có 40% điểm tương ứng với trường hợp ~5000 < N ≤ 10^6~.