Do quá chán trong những ngày nghỉ dịch, huyhau6a2 và bot huyhau7a2 đã phải chế những trò chơi mới để chơi. Và đây là một trong số chúng:

Bộ bài mà huyhau6a2 mới chế gồm có \(n\) thẻ bài, thẻ bài thứ \(i\) có giá trị \(a_i\). Luật chơi như sau:

• Các thẻ bài sẽ được đặt trên một hàng trước mặt họ từ \(1\) đến \(n\).
• Đầu tiên, huyhau6a2 sẽ chọn một cặp số \([l,r]\) \((l\leq r)\). huyhau6a2 sẽ được lấy tất cả các thẻ bài trong đoạn \([l,r]\).
• Tiếp theo, bot huyhau7a2 sẽ phải chọn một số \(j\) bất kỳ \((l\leq j\leq r)\). huyhau7a2 sẽ được lấy thẻ bài có số hiệu \(j\).
• Kết quả của trò chơi sẽ là tổng giá trị của tất cả các thẻ bài còn lại mà huyhau6a2 đã lấy.
• Trường hợp \(l=r\) (huyhau6a2 chỉ lấy một lá) thì kết quả của trò chơi sẽ là \(0\) do huyhau7a2 chỉ có thể lấy 1 lá duy nhất.

huyhau6a2 sẽ cố để tối đa hóa số điểm, trong khi đó bot huyhau7a2 sẽ cố để giảm thiểu số điểm.

huyhau6a2 muốn biết cách để đạt điểm tối đa nhưng mà do làm ra quá nhiều thẻ nên không biết phải lấy như thế nào. Các bạn hãy giúp huyhau6a2 nhé!

Input

• Dòng đầu tiên nhập số \(n\) cho biết số lượng thẻ bài.
• Dòng tiếp theo nhập \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) cho biết giá trị của các thẻ bài.

Output

• Duy nhất một số là số điểm tối đa huyhau6a2 có thể đạt được.

Constraints

• \(1\leq n\leq 10^6\)
• \(-30\leq a_i\leq 30\)

Scoring

• Subtask #1 (\(30\%\) số điểm): \(n\leq 10^3\).
• Subtask #2 (\(20\%\) số điểm): \(a_i\geq 0\).
• Subtask #3 (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

Sample input 1

5
5 -2 10 -1 4

Sample output 1

6

Sample input 2

3
-10 6 -15

Sample output 2

0

Note

• Trong ví du 1, huyhau6a2 sẽ lấy hết \(5\) thẻ trong bộ bài, bot huyhau7a2 sẽ lấy thẻ số \(3\) để được số điểm tối đa là \(5+(-2)+(-1)+4=6\).
• Trong ví dụ 2, huyhau6a2 có thể lấy duy nhất \(1\) thẻ bất kỳ trong bộ bài, bot huyhau7a2 phải lấy thẻ duy nhất đó để được số điểm tối đa là \(0\). Trường hợp lấy nhiều hơn \(1\) thẻ thì số điểm sẽ nhỏ hơn \(0\).

Nguồn: Lấy cảm hứng từ cốt phốt. Bài này chỉ là bản khó hơn ở phần dữ liệu thôi hehe