시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 21 | 11 | 10 | 58.824% |
Website chefforces.at
has just published a schedule of contests for the next year! There will be $n$ contests and no changes in the schedule. Oleg got really excited and decided to maximize the fun.
After a thorough analysis of each contest's problem setters Oleg came up with $n$ integers $a_i$, one for each contest. The number $a_i$ is the amount of fun Oleg will get while playing the $i$-th contest. Note that, due to a notorious coincidence, some numbers $a_i$ can be negative.
However, Oleg does not want to miss contests and, especially, to miss several contests in a row. Formally, if Oleg decides to skip a contest, and he has already skipped $x$ contests which took place immediately before this one, his total fun decreases by $x + 1$.
Finally, Oleg wants each contest to be at least as fun as the previous one in which he has participated. In other words, if Oleg participates in contests with numbers $i$ and $j$, $i < j$, then the condition $a_i \leq a_j$ must hold.
Help Oleg to decide in which contests he has to participate in order to maximize the total fun.
The first line contains an integer $n$, the number of contests in the schedule ($1 \leq n \leq 10^5$).
The second line contains $n$ integers $a_i$ ($-10^9 \leq a_i \leq 10^9$).
The only line of the output must contain an integer: the maximal amount of fun Oleg can get.
7 1 3 2 7 3 2 4
7
7 -3 -4 -2 -2 -6 -8 -1
-11