Problem : 149 - 改建路徑

Problem Statistics

Solved Member: 8　　Submission: 48　　User Tried: 10

Statement:

Farmer John 正在闢建他農田的小路，小路是由長 n 公尺的路徑所構成的。
路徑的每一公尺有不盡相同的高度，分別為 A1,A2, ... ,An 公尺高。由於 Farmer John 非常喜歡運動，他希望將這條路變成上坡的路徑。更詳細地說，他要將小徑變成 B1,B2, ... ,Bn 公尺高，使得 B1 ≤ B2 ≤ ... ≤ Bn。

每將一公尺的地從 Ai 公尺高改建為 Bi公尺高需要花 |Bi - Ai|單位的力氣，Farmer John想知道，他究竟需要花費多少力氣才能將路徑變成他所想要的。

Input:Output:

第 1 行有一個正整數 n(n ≤ 3000000)。
接下來 n 行分別代表 A1 到 An 的值，其中 0 ≤ Ai ≤ 10^9。

輸出一個數字，代表最少需要花費的力氣。

Sample Input:Sample Output:

7
1
3
2
4
5
3
9

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1000ms	196608kb
1-1	1000ms	196608kb	10
1-2	1000ms	196608kb
2-1	1000ms	196608kb	10
2-2	1000ms	196608kb
3-1	1000ms	196608kb	10
3-2	1000ms	196608kb
4-1	1000ms	196608kb	10
4-2	1000ms	196608kb
5-1	1000ms	196608kb	10
5-2	1000ms	196608kb
6	12000ms	196608kb	10
7	12000ms	196608kb	10
8	12000ms	196608kb	10
9	12000ms	196608kb	10
10	12000ms	196608kb	10