Problem D
Bungee Builder

A new bungee jumping attraction is to be built at a mountain range of $N$ mountains of heights $H_1,H_2,\dots ,H_N$. This project involves constructing a horizontal bridge connecting two distinct mountains, on which the attraction will be opened. The bridge may be built at any height up to the minimum of the two connecting mountains as long as it is strictly higher than all mountains between the two.

Once the bridge is built, the attraction will be opened at some point along it. The jumping distance is limited by the vertical distance of the attraction from the ground directly below. In order to achieve the greatest level of excitement, the bridge should be built to maximise the distance of the furthest point from the ground.

Consider the following example:

The optimal bridge is denoted by the solid red line and the jumping distance is denoted by the dotted red line.

Your task is to determine the maximum jumping distance achievable. If no bridge can be built, the distance is zero.

Input

The first line contains an integer $N$ ($1\le N\le {10}^6$), the number of mountains. The second line contains $N$ integers $H_1,H_2,\dots ,H_N$ where $H_i$ ($0\le H_i\le {10}^9$) denotes the height of the $i^{\text{th}}$ mountain.

Output

The maximum jumping distance possible.

Subtasks

1. (25 Points): $1\le N\le {10}^2$

2. (50 Points): $1\le N\le {10}^3$

3. (25 Points): No additional constraint

10
3 5 1 4 2 3 7 2 2 5

4