Aesthetic Progression

Alek has solved a_i problems of difficulty i on the online judge Code Power. He now wishes that his problem counts form an arithmetic progression with non‐positive common difference (i.e. \(d \le 0\)). In order to achieve this, he can solve extra problems. Although he is capable of solving 42 problems in a day, he wants to minimize the total number of extra problems he needs to solve.

Formally, you are given an integer n and a sequence of integers \(a_1, a_2, \dots, a_n\). You are allowed to add a nonnegative integer \(x_i\) to each \(a_i\) so that after doing so, they satisfy \[ a_i+x_i=s+(i-1)d \] for some integers \(s\) and \(d\) with \(d\le 0\). Your task is to choose \(x_i\) (and thus \(s\) and \(d\)) so that the total number of extra problems \(\sum_{i=1}^n x_i\) is minimized. You may assume that there is an unlimited supply of problems of any difficulty.

Input Format: The first line contains an integer n. The second line contains n integers \(a_1, a_2, \dots, a_n\).

Output Format: Output a single integer, the minimum number of extra problems Alek must solve.

Note on the common difference: The arithmetic progression must have a non‐positive common difference, i.e. \(d \le 0\).

inputFormat

The first line contains a single integer n (the number of difficulties).

The second line contains n space-separated integers \(a_1, a_2, \dots, a_n\) representing the number of problems solved for each difficulty.

outputFormat

Output a single integer, the minimum number of extra problems Alek needs to solve to make the sequence form an arithmetic progression with a non-positive common difference.

sample

5
1 2 3 4 5

10