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