# Problem F

Olympus Måns

Languages
da
en
Your Swedish friend Måns loves to take pictures of himself with mountaintops (or at least hilltops) in the background. Måns owns a tripod on which he can mount the camera at a height of up to $4$ feet. He wants to include the highest mountaintop in the picture. How far away from the start of the mountain does he have to stand?

## Input

On the first line, the number $n \geq 2$ of heights in the mountain’s height profile. The second line consists of $n$ integers $h_1, \ldots , h_ n$, which describe the mountain’s height profile from Måns’ initial position at the start of the mountain. There is $1$ foot horizonatally between each point in the profile, and we assume that these points are connected by straight lines.

The mountain is guaranteed to have a unique top, i.e., the maximal number among $h_1$, $\ldots $, $h_ n$ occurs only once. Moreover, we have $h_ i\geq 0$ for all $i$.

Initially, Måns is standing at the first point, i.e., at height $h_1$, and must move away from the mountain until it is possible to take a picture in which the mountaintop is visible. The surroundings of the mountain are flat, so that the tripod will be placed at height $h_1$. Do not take the curvature of the planet into account.

The tripod can have any length between (and including) $0$ and $4$ feet.

## Output

Print a single integer: the smallest number $l\geq 0$, such that the mountaintop is visible if Måns places his tripod $l$ feet further away from the top, relative to $h_1$.

## Points

There are three test groups, depending on whether Måns’ spends his holiday in Denmark, the Himalayas, or on Mars.

Group |
Points |
Constraints |

1 |
32 |
$h_ i \leq 600$ feet, $n\leq 1\, 000$ |

2 |
33 |
$h_ i \leq 30\, 000$ feet, $n\leq 10\, 000$ |

3 |
35 |
$h_ i \leq 72\, 000$ feet, $n\leq 100\, 000$ |

## Explanation of samples 1 and 2

The sample inputs can be drawn as

In Sample 1, Måns just barely can include the mountaintop by putting the tripod $2$ feet away from $h_1$. If he were to move $1$ foot closer, the point $h_2=5$ would be in the way, spoiling the view.

In Sample 2, he can remain where he is.

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

6 0 5 5 6 4 0 |
2 |

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

8 10 12 9 12 12 13 11 10 |
0 |