Підпослідовність із максимальною сумою

Задано послідовність $a_1,a_2,...,a_n$ довжини $n$. Знайдіть таку її послідовність $a_{i_1},a_{i_2},...,a_{i_k}$, що

• числа в послідовності відсортовані в строго зростаючому порядку.

• сума чисел підпослідовності $a_{i_1}+a_{i_2}+...+a_{i_k}$ найбільша

Вхідні дані

Перший рядок містить довжину послідовності $n(n\le 10^4)$. Другий рядок містить $n$ цілих чисел $a_i(0\le a_i\le 10^5)$.

Вихідні дані

Виведіть суму максимальної послідовності.

Приклади

Наприклад, для послідовності $\{3,2,100,4,5,6\}$ відповідь $103=3+100$.