# Problem H

Highest Hill

Sweden may not have a particularly impressive mountain range
compared to other NCPC countries such as Norway and Iceland,
but at least it beats the flatlands of Denmark. The situation
is not so clear when comparing other member countries though.
For example, is Estonia more mountainous than Lithuania^{1}? To settle this question, you want
to determine which of the two countries has the most impressive
mountain peak.

A mountain range is defined by sampling the heights
$h_ i$ of $n$ equidistant points. Within a
mountain range, we call a triple of indices $1 \le i < j < k \le n$ a
*peak* if $h_ i \leq \cdots \leq h_ j \geq \cdots \geq
h_ k$. The *height* of a peak is
defined as the smaller of $h_ j -
h_ i$ and $h_ j-h_
k$.

Given a mountain range, can you find the height of its highest peak?

## Input

The first line contains a single integer $N$ ($3 \le n \le 200\, 000$), the number of sampled points of the mountain range.

The second and final line contains the heights $h_1, \dots , h_ N$ ($0 \le h_ i \le 318 \cdot 10^9$) of the sampled points, in nanometers above sea level.

It is guaranteed that the mountain range contains at least one peak.

## Output

Output a single integer: the height of the highest peak.

Sample Input 1 | Sample Output 1 |
---|---|

11 0 1 2 3 4 5 4 3 2 1 0 |
5 |

Sample Input 2 | Sample Output 2 |
---|---|

10 29 85 88 12 52 37 19 86 7 44 |
67 |

Sample Input 3 | Sample Output 3 |
---|---|

3 2147483647 318000000000 2147483647 |
315852516353 |

Sample Input 4 | Sample Output 4 |
---|---|

3 1 1 1 |
0 |

**Footnotes**

- Yes, but not by much! The highest point in Lithuania is Aukštojas Hill, $293.84$ meters above sea level, while Estonia has the highest peak in the Baltics: Suur Munamägi is $318$ meters above sea level.