Given a sequence $a_1, a_2, ..., a_n$ of length $n$. Find its subsequence $a_{i_1}, a_{i_2}, ..., a_{i_k}$ such that \begin{itemize} \item the numbers in the subsequence are sorted in strictly ascending order. \item the sum of numbers in the subsequence $a_{i_1} + a_{i_2} + ... + a_{i_k}$ is the biggest \end{itemize} \InputFile The first line contains the size of array $n~(n \le 10^4)$.The second line contains $n$ integers $a_i~(0 \le a_i \le 10^5)$. \OutputFile Print the sum of the maximum sum subsequence. \Examples For example, if input is $\{3, 2, 100, 4, 5, 6\}$, then output should be $103~(3 + 100)$.