Froglet Billy
Billy the Frog was sitting on a rock, enjoying the sunset, when he realized he was hungry. Looking around, he noticed gnats buzzing by the stream next to him. The stream is represented as a line, and the rock where Billy sits is part of this line. Billy, feeling very hungry, decided he wanted to eat all the gnats. Fortunately, Billy has a very long tongue, allowing him to eat any gnat without leaving the rock, though he can only eat one at a time.
However, extending his tongue over long distances requires effort, as Billy uses one unit of energy for each centimeter his tongue stretches. Each time Billy eats a gnat from a specific point, the following occurs: all gnats to the left of the eaten gnat and all gnats to the right of it jump one centimeter away from the spot in fear. The gnats at the same point as the eaten one are too shocked to move.
If a gnat jumps onto the rock where Billy is sitting, Billy eats it immediately without using any energy. In this case, the other gnats do not move.
Billy the Frog wants to know the minimum amount of energy he needs to consume all the gnats. Help him determine this.
Input
The first line of the input contains a single natural number n (1 ≤ n ≤ 100000) — the number of gnats. The second line contains n natural numbers, representing the distance of each gnat from the rock. All gnats are positioned on a straight line on one side of the rock, and the distances are given in non-decreasing order. The distances do not exceed 10^9.
Output
Output a single number — the minimum amount of energy Billy needs to eat all the gnats.