3. Art Object
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

An art object consists of $$$n$$$ columns with heights $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ centimeters. Critics believe that the art object will look better if the column heights are nondecreasing, that is, the height of each column must be no less than the height of the previous one ($$$a_i \ge a_{i-1}$$$ for all $$$i \ge 2$$$).

Since the order of the columns cannot be changed (this would destroy the author's idea), the columns can be placed on a staircase whose step height is $$$d$$$. In this case, one column will stand on each step, and the first column must stand on the first step. Then the height of the first column $$$a_1$$$ increases by $$$d$$$, the height of the second column $$$a_2$$$ increases by $$$2d$$$, the value of $$$a_3$$$ increases by $$$3d$$$, and so on.

To keep the art object from becoming too bulky, it is necessary to find the minimum suitable step height $$$d$$$ such that the column heights become nondecreasing.

Input

The first line of the input contains an integer $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$) — the number of columns.

The next $$$n$$$ lines contain the heights of the columns $$$a_i$$$, $$$1\le a_i \le 10^9$$$.

Output

The program must output the minimum suitable step height $$$d$$$. If the column heights are already nondecreasing, output $$$0$$$.

Scoring

Solutions that work correctly for $$$n \le 2$$$ will be awarded $$$20$$$ points.

Solutions that work correctly for $$$a_i \le 10$$$ will be awarded $$$30$$$ points.

Example
Input
5
1
5
2
7
5
Output
3
Note

In the first example, the column heights are $$$1, 5, 2, 7, 5$$$. If a staircase with step height $$$d=3$$$ is used, the column heights become $$$4, 11, 11, 19, 20$$$. If step height $$$d=2$$$ is used, the heights become $$$3, 9, 8, 15, 15$$$, and then column number 2 will be higher than column number 3.