Hide

# Olympus Måns

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

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
CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 5.3 - 6.7hard
Statistics Show