Bergur

Hot Yoga

Bergur는 약간의 지방을 태우기 위해 Hot Yoga에 가기로 했다. Bergur는 단지 규칙적으로 Hot Yoga에 가는 것만으로는 충분히 멋지지 않다고 생각하여, 오늘 Hot Yoga에서 보내는 시간을 지난날에 보낸 시간보다 길거나 같게 하려고 한다. 즉, Bergur는 앞으로 $N$일 동안 하루도 빠짐없이 매일 Hot Yoga에 갈 예정이다. 각 날짜에 Hot Yoga에서 보낼 수 있는 최대 시간이 주어지며, $i$번째 날에는 $a_i$로 정의된다. 하지만 Bergur가 그보다 짧게 있어도 된다.

Bergur는 이 $N$일 동안 Hot Yoga에서 가능한 한 오래 있고 싶지만, 항상 전날보다 Hot Yoga에서 보내는 시간이 길거나 같아야 한다는 조건도 만족해야 한다.

다시 말해, Bergur가 매일 Hot Yoga에서 보내는 시간은 감소하지 않는다.

점수

그룹 | 점수 | 제한

1 | 50 | $N \leq 1\,000$

2 | 50 | 추가 제한 없음

입력의 첫 번째 줄에는 날짜 수를 나타내는 하나의 정수 $N$ ($1 \leq N \leq 3 \cdot 10^5$)이 주어진다.

다음 줄에는 $N$개의 수 $1 \leq a_i \leq 10^4$가 주어지며, $i$번째 수는 해당 날짜에 Bergur가 운동할 수 있는 최대 시간을 나타낸다.

위에서 정의한 규칙을 어기지 않고 Bergur가 운동할 수 있는 최대 총시간을 나타내는 하나의 정수를 출력한다.