Để chuẩn bị cho ngày đại lễ Giỗ Tổ Hùng Vương, chàng Lang Liêu chuẩn bị ~n~ món lễ vật quý giá được đánh số từ ~1~ đến ~n~. Mỗi món lễ vật thứ ~i~ có giá trị tinh hoa là ~a_i~.

Lang Liêu muốn chọn ra một số món lễ vật để dâng lên các Vua Hùng sao cho sự thành kính ngày càng tăng tiến. Cụ thể, nếu món lễ vật được chọn sau có thứ tự lớn hơn món trước đó, thì giá trị tinh hoa của nó cũng phải lớn hơn món trước.

Yêu cầu: Hãy giúp Lang Liêu chọn các món lễ vật sao cho tổng giá trị tinh hoa của các món được chọn là lớn nhất

Input

• Dòng ~1~: chứa số nguyên dương ~n~ ~(1 \le n \le 10^5)~;

• Dòng ~2~: chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(0 \le a_i \le 10^9, 1 \le i \le n)~, mỗi số cách nhau một dấu cách.

Output

Một số nguyên duy nhất là tổng giá trị tinh hoa lớn nhất.

Scoring

Sample Input 1

6
1 7 2 7 8 5

Sample Output 1

18

Notes

Chọn các ngày: ~1, 3, 4, 5~ tương ứng với dãy con ~1, 2, 7, 8~.