시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 7 4 4 100.000%

문제

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.

예제 입력 1

7
1 3 2 7 3 2 4

예제 출력 1

7

예제 입력 2

7
-3 -4 -2 -2 -6 -8 -1

예제 출력 2

-11