Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

A. Minimum Difficulty

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputMike is trying rock climbing but he is awful at it.

There are *n* holds on the wall, *i*-th hold is at height *a*_{i} off the ground. Besides, let the sequence *a*_{i} increase, that is, *a*_{i} < *a*_{i + 1} for all *i* from 1 to *n* - 1; we will call such sequence a track. Mike thinks that the track *a*_{1}, ..., *a*_{n} has difficulty . In other words, difficulty equals the maximum distance between two holds that are adjacent in height.

Today Mike decided to cover the track with holds hanging on heights *a*_{1}, ..., *a*_{n}. To make the problem harder, Mike decided to remove one hold, that is, remove one element of the sequence (for example, if we take the sequence (1, 2, 3, 4, 5) and remove the third element from it, we obtain the sequence (1, 2, 4, 5)). However, as Mike is awful at climbing, he wants the final difficulty (i.e. the maximum difference of heights between adjacent holds after removing the hold) to be as small as possible among all possible options of removing a hold. The first and last holds must stay at their positions.

Help Mike determine the minimum difficulty of the track after removing one hold.

Input

The first line contains a single integer *n* (3 ≤ *n* ≤ 100) — the number of holds.

The next line contains *n* space-separated integers *a*_{i} (1 ≤ *a*_{i} ≤ 1000), where *a*_{i} is the height where the hold number *i* hangs. The sequence *a*_{i} is increasing (i.e. each element except for the first one is strictly larger than the previous one).

Output

Print a single number — the minimum difficulty of the track after removing a single hold.

Examples

Input

3

1 4 6

Output

5

Input

5

1 2 3 4 5

Output

2

Input

5

1 2 3 7 8

Output

4

Note

In the first sample you can remove only the second hold, then the sequence looks like (1, 6), the maximum difference of the neighboring elements equals 5.

In the second test after removing every hold the difficulty equals 2.

In the third test you can obtain sequences (1, 3, 7, 8), (1, 2, 7, 8), (1, 2, 3, 8), for which the difficulty is 4, 5 and 5, respectively. Thus, after removing the second element we obtain the optimal answer — 4.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/15/2018 11:11:33 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|