Cho dãy \(A\) gồm \(N\) phần tử là các số nguyên dương \(A_1, A_2, ..., A_N\). Dãy \(C\) được gọi là dãy con tăng độ dài \(K\) của \(A\) nếu thoả mãn các điều kiện sau:

• \(K \geq 1\).
• \(1 \leq i_1 < i_2 < i_3 < ... < i_K \leq N\).
• \(C_1 = A_{i_1}, C_2 = A_{i_2}, ..., C_K = A_{i_K}\).
• \(C_1 < C_2 < ... < C_K\) nếu \(K \geq 2\)

Yêu cầu: Gọi \(SumC = \sum\limits_{i=1}^K C_i\). Tìm \(SumC\) lớn nhất có thể của dãy \(C\).

Input

• Dòng thứ nhất gồm số nguyên dương \(N\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, A_3, ..., A_N\).

Output

• In ra một số nguyên dương duy nhất là kết quả bài toán.

Constraints

• \(N\leq 10^5\)
• \(A_i\leq 10^9\)

Scoring

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

Example

5
1 2 3 5 4 

11