문제1756--The level adjustment

1756: The level adjustment

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 34  통과: 26
[제출] [채점기록] [묻고답하기]

문제 설명

 

Ryuju 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. Ryuju 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, Ryuju 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 Ryuju 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 input consists of T test cases. The number of test cases T is given in the first line of the input.
 
The first line of each test case contains one positive integer N ( 1 ≤ N ≤ 100 ), the number of levels.
 
The next N lines of each test case contains positive integers less than 20,000, the number of points that Ryuju has associated with each level, from the first to the last level.
 

출력 설명

 

The first and only line of output of each test case should contain one number -- the minimum total number of points Ryuju has to subtract to fulfill requirements given in the task statement above.
 

입력 예시 Copy

2
3
5
5
5
4
5
3
7
5

출력 예시 Copy

3
6

출처/분류