누텔라의 인생

웹사이트 chefforces.at이 내년 대회 일정을 방금 발표했다. 대회는 $n$개가 열리고 일정은 바뀌지 않는다. 올레그는 매우 신이 나서 재미를 최대로 만들기로 했다.

각 대회의 출제진을 꼼꼼히 분석한 올레그는 대회마다 정수 $a_i$를 하나씩 정했다. $a_i$는 $i$번째 대회를 치를 때 올레그가 얻는 재미의 양이다. 악명 높은 우연 때문에 일부 $a_i$는 음수일 수 있다.

그런데 올레그는 대회를 놓치고 싶지 않고, 특히 여러 대회를 연속으로 놓치고 싶지 않다. 형식적으로, 올레그가 어떤 대회를 건너뛰기로 했고 바로 그 앞에서 열린 대회를 이미 $x$개 건너뛰었다면, 총 재미는 $x + 1$만큼 줄어든다.

마지막으로, 올레그는 각 대회가 자신이 참가한 바로 이전 대회보다 재미있기를 바란다. 다시 말해, 올레그가 $i$번째와 $j$번째 대회에 참가하고 $i < j$라면 $a_i \leq a_j$가 성립해야 한다.

올레그가 총 재미를 최대로 만들기 위해 어떤 대회에 참가해야 하는지 결정하도록 도와주자.

첫째 줄에는 일정에 있는 대회의 수 $n$이 주어진다 ($1 \leq n \leq 10^5$).

둘째 줄에는 $n$개의 정수 $a_i$가 주어진다 ($-10^9 \leq a_i \leq 10^9$).

올레그가 얻을 수 있는 최대 재미의 양을 정수 하나로 출력한다.