芳芳的不下降序列

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

 

芳芳特喜欢数列,有一天,芳芳发现了这样一个问题,给一个n个数的序列,可以进行这样一次操作,对区间[L,R]上的数字集体+11<=L<=R<=n),最少操作多少次,使得整个序列变为单调不下降序列。

3 2 1 -> 3 3 2 -> 3 3 3最少2次操作。

无所不能的芳芳觉得太简单了,你能解决吗?

Input

 

多组数据。输入一个n,接下来有n个数字。(1<=n<=10000,这些数字不会超int)

Output

 

每组输出一个数字,最小的操作数。

Sample Input

3
1 2 3
3
3 2 1
4
7 4 1 47

Sample Output

0
2
6

Hint

 

Source

cuizhe