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? 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}h\_i$ of $nn$ equidistant points. Within a mountain range, we call a triple of indices a peak if $h_i\le \cdots \le h_j\ge \cdots \ge h_{k}h\_i\; \backslash leq\; \backslash cdots\; \backslash leq\; h\_j\; \backslash geq\; \backslash cdots\; \backslash geq\; h\_k$. The height of a peak is defined as the smaller of $h_j-h_{i}h\_j\; -\; h\_i$ and $h_j-h_{k}h\_j-h\_k$.

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

입력

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

The second and final line contains the heights $h_1,\dots ,h_{N}h\_1,\; \backslash dots,\; h\_N$ ($0\le h_i\le 318\cdot {10}^{9}0\; \backslash le\; h\_i\; \backslash le\; 318\; \backslash 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 a single integer: the height of the highest peak.

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

5

10
29 85 88 12 52 37 19 86 7 44

67

3
2147483647 318000000000 2147483647

315852516353

3
1 1 1

0