Wall

The firm <> is developing artificial intelligence for a new automated model of an industrial robot, SCV-2. At this stage it is building a robot that constructs and repairs walls made of standard building blocks.

First they decided to make a simplified robot model that works with walls consisting of blocks of equal size. A wall is a sequence of columns made of blocks; an example of such a wall is shown in Figure 1.

Figure 1

The first robot model can perform exactly one elementary action: take the top block of some column and put it on an adjacent column. It is not allowed to create a new column by placing a block next to the edge of the wall.

As a test task for the artificial intelligence, the problem of leveling a wall was posed. A wall is called level if the heights of any two columns differ by at most one. In the process of leveling, the robot must use elementary actions to turn the given wall into any level wall. The number of elementary actions performed must be minimal, and the number of columns in the wall must not change.

For example, the wall shown in Figure 1 can be turned into the level wall shown in Figure 2 in four elementary actions, and this number of actions is minimal for that wall.

Figure 2

Help the artificial intelligence developers verify the algorithm they wrote: find the minimum number of actions the robot will have to perform to level the given wall.

The first line of the input contains the integer $n$ ($1 \le n \le 1000$), the number of vertical rows that make up the wall. The second line contains the numbers $a\_1, a\_2, \ldots, a\_n$, where $a\_i$ is the number of blocks in the $i$-th column ($1 \le a\_i \le 10^6$).

Print a single integer: the minimum number of block moves needed to level the wall.