OMG爱吃鸡

Time Limit: 3000ms

Memory Limit: 65536KB

Description

  OMG 爱吃鸡。他要在n天里每天吃一只鸡。每天要吃的鸡分别有Ai的美味度。   但是他是一个有品位的人,他要求每天吃的鸡的美味度都不低于前一天的美味度。(第一天任意)   所以膜法师GG需要修改(增加或者降低或者不变)每只鸡的美味度,来满♂足他。现要求修改的美味度总和最少,求总和。

Input

  多组case,每组case第一行输入一个n,第二行输入n个数( 1<=n <= 2000, 数的范围[0,1e9])

Output

  输出修改的美味度总和

Sample Input

7
1 3 2 4 5 3 9

Sample Output

3

Hint

None

Source

None

提交代码