Strictly Increasing Sequence Adjustment

You are given an array of integers ( a = [a_1, a_2, \dots, a_n] ). You are allowed to choose a non-negative integer ( k ) and transform the array into another array ( b ) defined as:

[ b_i = a_i + i \cdot k \quad \text{for } i = 1,2,\dots,n. ]

Your task is to find the smallest non-negative integer ( k ) such that the resulting array ( b ) is strictly increasing, that is,

[ b_1 < b_2 < \cdots < b_n. ]

It is guaranteed that a solution always exists.

Note: The index ( i ) is 1-based. For example, if ( a = [1, 2, 2, 3] ), then for ( k = 1 ) we obtain ( b = [1+1,; 2+2,; 2+3,; 3+4] = [2, 4, 5, 7] ), which is strictly increasing.

inputFormat

The input is given via standard input (stdin). The first line contains an integer ( n ) (the number of elements in the array). The second line contains ( n ) space-separated integers representing the array ( a ).

outputFormat

Output a single integer, the smallest non-negative integer ( k ) such that the array ( b ), defined by ( b_i = a_i + i \cdot k ) for ( i = 1,2,\dots,n ), is strictly increasing. The output should be written to standard output (stdout).## sample

5
1 2 3 4 5

0