Robot

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ứ nhất, robot sẽ nhảy lên các viên gạch dọc theo hàng và nhảy đến viên gạch cuối cùng (viên gạch thứ \(N\)). Tuy nhiên do hạn chế về kỹ thuật và năng lượng, bước nhảy tiếp theo của Robot không thể dài hơn bước vừa nhảy ngay trước đó, tức là 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ì \(k - j \le 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. Vị trí xuất phát của Robot là viên đầu tiên, vị trí kết thúc của Robot là viên cuối cùng.

Input

Dữ liệu vào gồm \(2\) dòng:

• Dòng đầu tiên chứa số nguyên dương \(N\) là số lượng viên gạch (\(1 \le N \le 10^4\)).

• Dòng thứ hai chứa \(N\) giá trị \(A_1, A_2, \ldots, A_N\) là giá trị trên các viên gạch lần lượt từ viên đầu tiên đến viên cuối cùng (\(-10^9 \le A_i \le 10^9\)).

Ràng buộc:

• Subtask 1: \(1 \le N \le 20\).

• Subtask 2: \(20 \le N \le 500\).

• Subtask 3: Không ràng buộc gì thêm.

Output

In ra 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 gạch đầu tiên và viên gạch cuối cùng).

Example

Input:

6
1 -1 5 -2 -1 2

Output:

7

Note

Tổng giá trị các viên gạch mà robot đã nhảy tới: \(1 + 5 + (-1) + 2 = 7\).