Mario is at the final stage 999. Like most pay-2-play games, he now needs to purchase some stamina in order to complete this level.

Mario can jump from $i^{th}$ pipe to $(i+1)^{th}$ pipe if the absolute difference, or the difference in heights between H[i] & H[i+1] is less than or equal to current stamina.

Mario's stamina will decrease by 1 under two conditions:

1) He jumps a height equal to his current stamina, i.e. $distance = abs(H[i]-H[i+1])$

2) He jumps the same height more than once, i.e the jumped distance of abs(H[i] - H[i+1]) has occurred for some j<i.

3.) If conditions 1 and 2 occur simultaneously then stamina will decrease by only 1.

NOTE:

1.)Mario cannot jump if the distance is more than his current stamina.

2.)Mario starts from the first pipe, and he cannot skip any pipe, i.e he can only jump to the next pipe.

Help Mario decide the minimum amount of stamina he will have to purchase to complete this stage.

Input :

N, number of pipes

Array H consisting of N spaced integers.

Constraints :

2<=N<=10^5

1<=H<=10^6

Output :

Minimum stamina required to complete this level