Minimum increments

Given array with $n$ positive integers. Find the minimum number of operations required so that an Arithmetic Progression with the array elements is achieved with common difference as $1$. In a single operation, any element can be incremented by $1$.

Input

First line contains number $n(n\le 10^6)$. Second line contains $n$ positive integers, each is no more than $10^6$.

Output

Print the minimum number of operations to get an Arithmetic Progression with common difference as $1$.

Examples

In the first test array must be converted to $89101112$. In this case we'll make $(8-3)+(9-6)+(10-4)+(11-11)+(12-5)=5+3+6+0+7=21$ operations.