Hide

Problem G
Olympus Måns

Languages da en
/problems/olympusmans/file/statement/en/img-0001.jpg
Olympus Mons on Mars. Source: ESA/DLR/FU Berlin (G. Neukum), CC BY-SA 3.0 IGO.

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

\includegraphics[width=0.25\textwidth ]{img/sample1.pdf} \includegraphics[width=0.25\textwidth ]{img/sample2.pdf}

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