Simon the Giant

Simon is a construction worker Giant who is interested in making patterns of everything he sees, no matter how pointless they are. Simon, being irritated by the way humans have constructed a series of buildings in his homeworld, decides to use his Giant magic to alter them in his own way by adding to or taking away stories from the buildings such that every building has an equal or greater amount of stories than the one before it. (Note that it may exist buildings with 0 stories)

Using his Giant magic once which consumes 1 credit, Simon can alter a building by either adding or removing a single story.

What is the minimum amount of credits that Simon should consume to attain his desired pattern of buildings?

Input Format

• The first line contains a single integer N denoting the number of buildings.
• Second line contains N number of space separated integers, denoting the heights (h_i) of buildings.

Output Format

• Print the minimum amount of credits Simon should consume.

Constraints

• 1 \(\leq\) T \(\leq\) 5000
• 0 \(\leq\) h_i \(\leq\) 10⁹

Sample Input 0

5
3 2 1 2 11

Sample Output 0

2

Sample Input 1

2
10 2

Sample Output 1

8