프로그램 명: coci_razine
제한시간: 1 초
미코는 비디오 게임을 개발 했다.
게임은 N 레벨이 있고 각 레벨을 통과하면 포인터가 주어지고 이 포인터는 랭크가 부여되는 전체 점수에 누적이 된다.
미코는 가장 쉬운 난이도부터 점진적으로 가장 어려운 난이도로 레벨을 정하기로 했는데 실수를 해서 어려운 레벨에서 쉬운 레벨보다 더 적은 포인터를 가지게 하는 실수를 했다.
이 실수를 만회하기 위해 미코는 어떤 레벨의 포인터를 줄이기로 했다. 결과적으로 점진적으로 포인터가 늘어가야 한다.
미코를 도와 줄인 포인터의 합이 최소가 되도록 미코를 도와주는 것이 문제이다. 마지막 점수는 양수여야 하고 모든 테스트 케이스에서 답이 존재하는 것은 보장 된다.
Mirko has developed his own video game. The game has N levels and each successfully completed level is worth a certain number of points, which add up to the player’s total score on an online rank list of all players. Mirko has ordered his levels by difficulty from the easiest to the most difficult, but he has made a mistake and made some difficult levels worth less points than some of the easier ones.
To overcome this problem, Mirko has decided to reduce the number of points for certain levels with the goal of making the point sequence strictly increasing (so in the end easier levels are worth less points than the difficult ones).
Help Mirko fix his video game in such a way that the total number of points reduced is minimal. Final points have to be positive. You can assume that a solution exists for each test case.
입력
The first line of input contains one positive integer N (1 ≤ N ≤ 100), the number of levels.
The next N lines contain positive integers less than 20 000, the number of points that Mirko has associated with each level, from the first to the last level.
출력
The first and and only line of output should contain one number - the minimum total number of points Mirko has to subtract to fulfill requirements given in the task statement above.
입출력 예
input
3
5
5
5
output
3
input
4
5
3
7
5
output
6
출처:coci
[질/답]
[제출 현황]
[푼 후(0)]