C - Building a Wireless Network Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君は、N 個の基地局を使って無線ネットワークを構築しようとしています。基地局には 1 から N までの番号が付けられています。基地局は数直線上に設置されており、基地局 i は座標 X_i に位置しています。なお、どの 2 つの基地局も異なる座標に設置されています。

各基地局には同じ通信可能距離 K を持つ無線機器が設置されます。ここで K は非負整数です。2 つの基地局 i, j は、それらの間の距離が K 以下、すなわち |X_i - X_j| \leq K であるとき、直接通信が可能です。

高橋君は、任意の異なる 2 つの基地局の間で、直接通信または他の基地局を 1 つ以上中継することによって通信が可能であるようなネットワークを構築したいと考えています。より正確には、任意の異なる 2 つの基地局 s, t に対して、基地局の列 s = v_1, v_2, \ldots, v_m = t（m \geq 2）が存在し、連続する v_k と v_{k+1}（1 \leq k \leq m-1）がそれぞれ直接通信可能であるようにしたいということです。なお、N = 1 のときは基地局が 1 つしかないため、この条件は K の値によらず常に満たされます。

無線機器のコストを抑えるため、高橋君は通信可能距離 K をできるだけ小さくしたいと思っています。

すべての基地局の座標は整数であるため、条件を満たす K の最小値も必ず非負整数となります。この最小値を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq X_i \leq 10^9
  • X_i \neq X_j (i \neq j)
  • 入力はすべて整数

入力

N
X_1 X_2 \ldots X_N
  • 1 行目には、基地局の個数を表す整数 N が与えられる。
  • 2 行目には、各基地局の座標を表す N 個の整数 X_1, X_2, \ldots, X_N がスペース区切りで与えられる。

出力

すべての基地局間で互いに通信できるようになるための K の最小値を、1 行で出力せよ。

入力例 1

3
1 5 3

出力例 1

2

入力例 2

5
10 25 15 40 30

出力例 2

10

入力例 3

8
100 350 200 550 700 900 450 1000

出力例 3

200

Score : 300 pts

Problem Statement

Takahashi is trying to build a wireless network using N base stations. The base stations are numbered from 1 to N. The base stations are placed on a number line, and base station i is located at coordinate X_i. No two base stations are placed at the same coordinate.

Each base station is equipped with a wireless device that has the same communication range K, where K is a non-negative integer. Two base stations i and j can communicate directly if the distance between them is at most K, that is, |X_i - X_j| \leq K.

Takahashi wants to build a network such that any two distinct base stations can communicate, either directly or by relaying through one or more other base stations. More precisely, for any two distinct base stations s and t, there should exist a sequence of base stations s = v_1, v_2, \ldots, v_m = t (m \geq 2) such that consecutive stations v_k and v_{k+1} (1 \leq k \leq m-1) can each communicate directly. Note that when N = 1, there is only one base station, so this condition is always satisfied regardless of the value of K.

To reduce the cost of the wireless devices, Takahashi wants to make the communication range K as small as possible.

Since all base station coordinates are integers, the minimum value of K that satisfies the condition is guaranteed to be a non-negative integer. Find this minimum value.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq X_i \leq 10^9
  • X_i \neq X_j (i \neq j)
  • All input values are integers

Input

N
X_1 X_2 \ldots X_N
  • The first line contains an integer N, representing the number of base stations.
  • The second line contains N integers X_1, X_2, \ldots, X_N separated by spaces, representing the coordinates of each base station.

Output

Print in one line the minimum value of K required for all base stations to be able to communicate with each other.

Sample Input 1

3
1 5 3

Sample Output 1

2

Sample Input 2

5
10 25 15 40 30

Sample Output 2

10

Sample Input 3

8
100 350 200 550 700 900 450 1000

Sample Output 3

200