====== 게임을 만든 동준이 ======

===== 풀이 =====
  * i번째 레벨의 점수 a[i]가 i+1번째 점수 a[i+1]보다 크거나 같다면, a[i]=a[i+1]-1 이 되도록 감소시키면 된다.
  * 이렇게 a[i]를 감소시켰는데, a[i+1]을 또 감소시켜야 할 경우에는 a[i]를 거기에 맞춰서 다시 감소시켜야 하는 상황이 생긴다. 
  * 이것을 해결하는 쉬운 방법은 높은 레벨부터 점수를 확정시켜나가는 것이다. a[i+1]이 확정되었다면, 여기에 따라서 a[i]의 값을 확정시킬수 있다. 이 값은, a[0]~a[i-1]의 값이 이후에 어떻게 결정되든지 변하지 않는다. 따라서 모든 점수를 한번에 결정할수 있으므로 시간복잡도는 O(n).

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 2847. 게임을 만든 동준이".

- Problem link: https://www.acmicpc.net/problem/2847
- Solution link: http://www.teferi.net/ps/problems/boj/2847

Tags: [Greedy]
"""

INF = float('inf')


def main():
    N = int(input())
    points = [int(input()) for _ in range(N)]

    answer = 0
    prev = INF
    for point in reversed(points):
        if point >= prev:
            answer += point - prev + 1
            prev -= 1
        else:
            prev = point
    print(answer)


if __name__ == '__main__':
    main()

</dkpr>

{{tag>BOJ ps:problems:boj:실버_4}}