After having ruled the kingdom of Hastinapur for several years, Pandavas have decided to embark on the journey to heaven. The journey to heaven is not easy. The terrain is too tough and is full of ups and downs. At some locations the ground is way below the sea level while at other locations it is way above. Arjuna, the best archer in the world, can do miracles using his arrows. He can both raise or lower the ground level with his magical arrows. The max amount by which the arrows can raise or lower the altitude at each location depends upon the magical power which Arjuna binds with each one of them. Let this amount be X. So, the altitude at each location can be raised or lowered by any integral amount in the set [0, X] i.e. any integer from 0 to X inclusive. Arjuna has to keep this amount as small as possible, as greater value of this amount will make him weaker.

Heaven is located at very high altitude. So, Arjuna has to ensure that after using arrows, he adjusts the altitude of each location such that the altitude keeps on strictly increasing at the subsequent locations.

So, in this problem you will be given altitudes at each subsequent locations on Pandavas' journey to heaven in an array, H. You have to help Arjuna decide the smallest possible X so that he could use his arrows to either raise or lower altitude by an integral amount in [0, X] or do nothing at each of the locations, so that after having adjusted the altitudes at subsequent locations the array of altitudes is strictly increasing.

Input:
There are several test cases (<=50). Read until EOF.
Each test case has two lines. First line gives the number N of locations i.e. the size of the array H.
The second line lists N numbers, the elements of the array H i.e. the altitudes at the N locations. Negative values means below sea level.

Output:
For each test case, print one line the minimum value of X.

Constraints:
1<=N<=100000.
The altitudes can be any 32 bit signed integer.

Sample Input``` 3 1 2 2 5 5 2 3 1 4 3 1 2 3```

Sample Output``` 1 4 0```

Sample Explanation
For the second test case, each arrow can raise or lower the altitude at most by 4. At first location, the altitude would be reduced by 4. No reduction or raising would be required at the second and third locations. At, the fourth location an arrow would increase altitude by 3 and at the fifth location another arrow would increase the altitude by 1. So, final strictly increasing array would be "1 2 3 4 5".

Problem Setter : Dhruva Bhaswar

Languages: AWK,Bash,Brain,C,C++,Java,C#,JavaScript,Pascal,Perl,PHP,Python,Python3,Ruby,Text

Time Limit: 3 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Mode Judge

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0