수열 \(A\)가 주어졌을 때, 합이 가장 큰 증가하는 부분 수열을 구하려고 한다. 조건을 만족하는 부분 수열의 원소 합의 최댓값을 구하는 프로그램을 작성하시오.

증가하는 부분 수열의 정의

수열 \(A=(a_1,a_2,\dots,a_N)\)에서 일부 원소를 골라 만든 수열 \((a_{i_1},a_{i_2},\dots,a_{i_k})\)가 다음 두 조건을 모두 만족하면 증가하는 부분 수열이라고 한다.

1. 원소들은 원래 수열에서의 순서를 유지해야 한다. 즉, \(1 \le i_1 < i_2 < \dots < i_k \le N\)이어야 한다. 선택한 원소들이 서로 연속해 있을 필요는 없다.
2. 선택된 원소들은 뒤로 갈수록 반드시 엄격하게 커져야 한다. 즉, \(a_{i_1}<a_{i_2}<\dots<a_{i_k}\)를 만족해야 한다. 값이 같은 경우는 증가한 것으로 인정하지 않는다.

이 문제에서 가장 큰 증가하는 부분 수열은 길이가 가장 긴 수열을 뜻하지 않는다. 선택한 원소들의 합이 가장 큰 증가하는 부분 수열을 뜻한다.

예를 들어, 수열 \(A=\{50,60,1,2,3,4,5,90\}\)에서 \(\{1,2,3,4,5,90\}\)은 길이가 \(6\)이고 합이 \(105\)이다. 하지만 \(\{50,60,90\}\)은 길이가 \(3\)이고 합이 \(200\)이므로 합은 더 크다.

입력

첫째 줄에 수열 \(A\)의 크기 \(N\)이 주어진다.

둘째 줄에 수열 \(A\)를 이루는 \(A_i\)가 순서대로 주어진다.

출력

첫째 줄에 증가하는 부분 수열의 원소 합으로 만들 수 있는 최댓값을 출력한다.

제한 사항

• \(1 \le N \le 1,000\)
• \(1 \le A_i \le 1,000\)

예제 입력 1

10
1 100 2 50 60 3 5 6 7 8

예제 출력 1

113

예제 설명 1

\(\{1,2,50,60\}\)은 증가하는 부분 수열이며, 원소의 합은 \(1+2+50+60=113\)이다. 이보다 원소 합이 큰 증가하는 부분 수열은 만들 수 없다.