Cho mảng ~a~ gồm ~n~ số nguyên được đánh số từ ~1~ đến ~n~.

Trên trục nằm ngang ~Ox~ với chiều dương hướng từ trái sang phải, một robot tiến hành các thao tác di chuyển. Ban đầu tọa độ của robot tại ~0~. Robot tiến hành tổng cộng ~n~ thao tác di chuyển như sau:

• Thao tác ~1~: di chuyển ~a_1~ đơn vị theo chiều dương.
• Thao tác ~2~: di chuyển ~a_1~ đơn vị theo chiều dương, di chuyển ~a_2~ đơn vị theo chiều dương.
• Thao tác ~3~: di chuyển ~a_1~ đơn vị theo chiều dương, di chuyển ~a_2~ đơn vị theo chiều dương, di chuyển ~a_3~ đơn vị theo chiều dương.
• ~...~
• Thao tác ~i~: di chuyển ~a_1~ đơn vị theo chiều dương, di chuyển ~a_2~ đơn vị theo chiều dương, di chuyển ~a_3~ đơn vị theo chiều dương,~...~, di chuyển ~a_i~ đơn vị theo chiều dương.
• ~...~
• Thao tác ~n~: di chuyển ~a_1~ đơn vị theo chiều dương, di chuyển ~a_2~ đơn vị theo chiều dương, di chuyển ~a_3~ đơn vị theo chiều dương,~...~, di chuyển ~a_n~ đơn vị theo chiều dương.

Bạn hãy xác định tọa độ lớn nhất mà robot đã di chuyển đến.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 2 \times 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên của mảng ~a~ ~(- 10^8 \le a_i \le 10^8)~.

Output

• In ra tọa độ lớn nhất mà robot đã di chuyển đến.

Examples

Sample Input 1

3
2 1 -3

Sample Output 1

8

Sample Input 2

5
1 -1 1 -1 1

Sample Output 2

3

Notes

Trong ví dụ đầu tiên, thao tác di chuyển của robot như sau:

• Thao tác ~1~: di chuyển ~2~ đơn vị theo chiều dương đến tọa độ ~2~.
• Thao tác ~2~: di chuyển ~2~ đơn vị theo chiều dương đến tọa độ ~4~, di chuyển ~1~ đơn vị theo chiều dương đến tọa độ ~5~.
• Thao tác ~3~: di chuyển ~2~ đơn vị theo chiều dương đến tọa độ ~7~, di chuyển ~1~ đơn vị theo chiều dương đến tọa độ ~8~, di chuyển ~-1~ đơn vị theo chiều dương đến tọa độ ~7~.

Tọa độ lớn nhất mà robot đã di chuyển đến là ~8~.