M. Motorway Stops
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

For your next summer holidays, you are planning an exciting road trip covering the full length of the famous M6 motorway.

You have your route planned out to balance travel time between stops, but time is a little short so you will have to strike one of the stops from your itinerary and continue straight past it to the next one.

To make the longest drive between stops as short as possible, which stop should you eliminate from your itinerary?

Input

  • The first line of input contains the number of stops, $$$n$$$ ($$$3 \le n \le 200\,000$$$).
  • The second line of input contains $$$n$$$ integers in strictly-increasing order, $$$s_1 \ldots s_n$$$ ($$$0 \le s \le 10^9$$$) giving the cumulative distances of stops on your original route.

The first stop and last stop denote your start and end point respectively and cannot be skipped.

Output

Output the smallest integer distance between stops you can have, if you remove exactly one stop from the itinerary and it is not the first or last.

Examples
Input
5
0 50 125 175 236
Output
111
Input
4
100 300 600 10000
Output
9400