Jitu Bhaiya has to stand in for Prof. Roy, as he had to attend a medical emergency. Within the first 15 mins of the class, Jitu Bhaiya was able to gauge that the average IQ of class is higher than the students he regularly teaches. He gave a tricky question to the class and told them the first person to answer will be given a chocolate. The question description stated that - "You are given an array of integers. You have to convert this array into a consecutive sequence of increasing numbers , by applying two operations and without rearranging the array elements. Following are the two operations allowed on the array elements: Add or subtract K to a particular array element, where K can be any natural number There is a cost associated with each operation. Adding or subtracting K will cost K units. Can you find the minimum cost in which the given array can be transitioned into consecutive sequence of increasing numbers." Now, we present Jitu Bhaiya's problem to you. Can you solve it and win the coveted chocolate.
Input Format
First line of input contains an integer N. Next line contains N space-separated integers.
Output Format
A number representing the minimum cost.
Constraints
1 <= N <= 10^5 -10^5 <= arr[i] <= 10^5
Example
Input
5 7 7 10 2 9
Output
11