Призы

면접 대비

시간 제한1초메모리 제한1024 MB

요약

아무 지점에서 시작해 값이 엄격히 증가하는 부분 수열을 골라 얻는 보상 합의 최댓값을 구한다.

난이도: 보통10점 중 5점
유형: 동적 계획법
정답자: 아직 제출이 없습니다

문제

Миша участвует в процедуре награждения на интеллектуальном шоу. В процессе награждения ему последовательно предлагают призы. У каждого приза есть стоимость. Про каждый приз Миша должен заявить, хочет ли он его взять. После того, как Миша возьмет или пропустит приз, ему показывается следующий, и так далее, вернуться к предыдущим призам и изменить свое решение нельзя.

В качестве первого приза Миша может взять любой приз, а затем Миша может взять приз, если его стоимость строго больше стоимости предыдущего взятого им приза.

Миша подсмотрел сценарий шоу и знает стоимости призов, а также порядок, в котором они будут ему предлагаться. Помогите ему выбрать призы таким образом, чтобы их суммарная стоимость была как можно больше.

입력

Первая строка ввода содержит целая число $n$ --- количество призов ( $1 \le n \le 1000$ ). Вторая строка содержит $n$ чисел $a\_1, a\_2, \ldots, a\_n$ --- стоимости призов в том порядке, в котором их покажут Мише ( $1 \le a\_i \le 10^9$ ).

출력

Выведите одно число --- максимальную суммарную стоимость призов, которые может получить Миша.

예제1

예제 1
입력
```
5
4 2 3 6 6
```
예상 출력
```
11
```