Mind the Gap

Interview

Time limit2sMemory limit512 MB

Summary

Given n distinct positive card values, find an integer d so that the players, each playing their card exactly when its value is within d above the pile top and otherwise waiting, always place all cards in increasing order regardless of tie order.

Level: Medium7 of 10
Topics: Greedy, Sorting, Binary search, Array
Solved: No attempts yet

Problem

Mika is playing the Mind game with her friends.

The game is played with cards, and a single integer is written on each card. All values written on the cards are distinct. The players keep playing cards, building a single pile on the table. Initially the pile contains a single card with the integer $0$ on it. Each player is given a single card with a value from $1$ to $10^9$ . The players then start playing the cards in any order. When a player plays a card, they place it on top of the pile. The goal is to play all the cards so that the card values increase from the bottom to the top. If any player did not play their card, or the pile is not increasing, the players lose; otherwise they win. No communication between players is allowed after the cards are dealt.

Mika and her friends came up with a strategy. They agree on a single integer $d$ before the game. During the game, if a player's card value is $x$ and the top value of the pile is $y$ with $x - y \le d$ , the player plays their card. If $x - y > d$ , the player does not play their card. If several players play their cards at the same time, these cards might be placed on top of the pile in any order, and this order is not controlled by the players.

You are given the card values that will be dealt to the players. Find an integer $d$ for the players' strategy that guarantees them a win.

Input

The first line contains an integer $n$ , the number of players in the Mind game ( $3 \le n \le 100\,000$ ).

The second line contains $n$ integers, the card values dealt to the players.

All given card values are distinct, positive, and do not exceed $10^9$ .

Output

Print a single integer $d$ that Mika and her friends should use to guarantee a win in the game with their strategy. If no such $d$ exists, print $0$ . If several values of $d$ exist, print any of them.

Hint

In the first example, $d = 3$ would also be a correct answer.

Examples2

Example 1
Input
```
5
5 13 2 10 8
```
Expected output
```
4
```
Example 2
Input
```
5
4 13 2 8 7
```
Expected output
```
0
```