Please help me on this problem !

Revision en1, by I_love_Jiang, 2016-09-18 20:16:41

Link of the problem :http://www.spoj.com/problems/TOINCSEQ/

In short: You are given a sequence of non-negative integers a1, a2, …, an. You are allowed to perform some operators on the sequence. Each operator consists of 2 steps: choosing an arbitrary value, then increasing (or decreasing) all elements of the selected value in the current sequence by 1.

For example, the sequence 1 9 9 2 2 will become 1 9 9 3 3 if you decide to increase all elements of value 2.

What is the minimum number of operators does it take to make the given sequence a non-decreasing sequence?

Input

The first line consits of an integer N, the number of elements in the sequence. The second line consists of N elements of the sequence. Output

The mininum number of operators needed to make the sequence non-decreasing. Example

Input: 5

1 9 9 2 2

Output: 7 Constraints

1 ≤ N ≤ 10^5. Each element of the sequence is a non-negative integer not exceeding 10^9. ***************************************************************************

I think we can uses DP but I had no idea then.

Help me please !!!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English I_love_Jiang 2016-09-18 20:16:41 1154 Initial revision (published)