An thường đi chơi bowling với bạn bè. Hôm nay An cảm thấy thực sự tốt và cố gắng để đánh bại kỷ lục của chính mình!

Khi lăn một quả bóng, người chơi sẽ nhận được điểm là một số nguyên (có thể âm). Điểm của lần lăn bóng thứ ~i~ được nhân với ~i~, rồi cộng tất cả lại thì ta sẽ được tổng điểm của các lần chơi. Vì vậy nếu ~k~ lần lăn bóng có điểm là ~s_1, s_2, \dots, s_k~ thì tổng điểm là ~1 \times s_1 + 2 \times s_2 + \dots + k \times s_k~. Nếu không lần lăn bóng nào thì tổng điểm là ~0~.

An thực hiện ~n~ lần lăn bóng và đạt được ~a_i~ điểm cho lần lăn thứ ~i~. An muốn tối đa tổng số điểm của mình và anh ta đã đưa ra một ý tưởng thú vị. Anh ta nói rằng một số lần lăn bóng đầu tiên chỉ là khởi động và một số lần lăn cuối cùng anh ta không tập trung. Cụ thể, An có thể hủy bất kỳ tiền tố và bất kỳ hậu tố nào của dãy ~a_1, a_2, \dots, a_n~. Chú ý rằng An được phép hủy tất cả các lần lăn bóng hoặc không hủy lần lăn bóng nào.

Tổng điểm sẽ được tính với các lần lăn bóng không bị hủy. Vì vậy, lần lăn bóng không hủy đầu tiên có điểm nhân với ~1~, lần lăn bóng không hủy thứ hai có điểm nhân với ~2~ và cứ thế cho đến lần lăn bóng không hủy cuối cùng.

Bạn hãy tính xem An có thể đạt tổng điểm tối đa là bao nhiêu?

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 2 \cdot 10^5)~ là số lần An thực hiện lăn bóng.

• Dòng thứ hai chứa ~n~ số nguyên ~a_i~ ~(|a_i| \le 10^7)~ là các điểm của các lần lăn bóng.

Output

Ghi một số nguyên là tổng điểm tối đa sau khi đã hủy bỏ một số lần lăn bóng.

Scoring

Sample Input 1

6
5 -1000 1 -3 7 -8

Sample Output 1

16

Sample Input 2

5
1000 1000 1001 1000 1000

Sample Output 2

15003

Sample Input 3

3
-60 -70 -80

Sample Output 3

0

Notes

Trong ví dụ đầu tiên, An hủy ~2~ lần lăn bóng đầu tiên và ~1~ lần lăn bóng cuối cùng. Anh ta còn lại các lần lăn bóng với điểm là ~1, -3, 7~ và có tổng điểm là ~1 \cdot 1 + 2 \cdot (-3) + 3 \cdot 7 = 16~.