← 返回题目列表

AtCoder · awc0027_c

C. 构建无线网络

中文机器翻译题面 查看原题

分数: 300 分

问题陈述

Takahashi 正在尝试使用以下方式构建无线网络 N 基站。基站编号为 1 to N。基站放置在数轴上,并且基站 i 位于坐标 X_i。没有两个基站放置在同一坐标处。

每个基站均配备具有相同通信范围的无线设备 K,其中 K 是一个非负整数。两个基站 i 和 j 可以直接通信,如果它们之间的距离最大 K,即 |X_i - X_j| \leq K.

Takahashi 希望建立一个网络,使任何两个不同的基站都可以直接通信或通过一个或多个其他基站中继进行通信。更准确地说,对于任意两个不同的基站 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,只有一个基站,所以无论 的值如何,这个条件总是满足的 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
  • 第一行包含一个整数 N,代表基站数量。
  • 第二行包含 N 整数 X_1, X_2, \ldots, X_N 以空格分隔,代表各个基站的坐标。

输出

在一行中打印以下的最小值 K 要求所有基站能够相互通信。


示例输入 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