Задана последовательность $a_1, a_2, ..., a_n$ длины $n$. Найдите такую ее подпоследовательность $a_{i_1}, a_{i_2}, ..., a_{i_k}$, что \begin{itemize} \item числа в подпоследовательности отсортированы в строго возрастающем порядке. \item сумма чисел подпоследовательности $a_{i_1} + a_{i_2} + ... + a_{i_k}$ наибольшая \end{itemize} \InputFile Первая строка содержит длину последовательности $n~(n \le 10^4)$. Вторая строка содержит $n$ целых чисел $a_i~(0 \le a_i \le 10^5)$. \OutputFile Выведите сумму максимальной подпоследовательности. \Examples Например, для последовательности $\{3, 2, 100, 4, 5, 6\}$ ответ будет $103 = 3 + 100$.