Gần đây một trò chơi mới được du nhập vào Gensokyo, đó là chơi bài. Hôm nay Cirno cùng với Daiyousei sẽ thử chơi trò chơi mới này.

Bộ bài gồm có ~n~ lá bài được đặt trên bàn theo thứ tự từ trái sang phải, trên mỗi lá bài là một số nguyên, giá trị của lá bài. Cirno sẽ chọn một đoạn các lá bài từ ~l~ đến ~r~, sau đó Daiyousei sẽ chọn lá bài thứ ~j~ sao cho ~l \le j \le r~ và loại bỏ nó. Điểm nhận được là tổng các lá bài còn lại trong đoạn từ ~l~ đến ~r~.

Cirno muốn số điểm là lớn nhất có thể, còn Daiyousei lại muốn số điểm là nhỏ nhất có thể. Các bạn hãy giúp Cirno tìm cách chọn tối ưu để số điểm là lớn nhất nhé!

Input:

• Dòng đầu gồm số tự nhiên ~n~ là số lá bài.
• Dòng tiếp theo gồm ~n~ số nguyên ~a_i~ với ~1 \le i \le n~ là giá trị các lá bài.

Output:

• Một số nguyên điểm lớn nhất có thể.

Sample Test

Input 1:

5
5 -2 10 -1 4

Output 1:

6

Input 2:

3
-10 6 -15

Output 2:

0

Giới hạn:

• Trong tất cả các test: ~n \le 10 ^ 5, -10^9 \le a_i \le 10^9~.
• Subtask 1 (40%): ~n \le 1000~.
• Subtask 2 (30%): ~-30 \le a_i \le 30~.
• Subtask 3 (30%): Không có giới hạn gì thêm.