Background

我们不顾心灵桎梏，沉溺于人世浮华，专注于利益法则，我们把自己弄丢了。

Description

战争的艺术在于分割包围. 现在, 敌人的若干兵团排成一条线. 现在, 我们要肖灭一定数量 的兵团. 为了分割敌人, 我们要使得相距最近的敌人的两个兵团间的距离最大. 但是注意到战场节操问题, 我们不能攻击敌人最左端和最右端的敌人.

Format

Input

第一行包含三个整数 x, n, m(x ≤ 109, n ≤ 50, 000, m ≤ n). 表示最右端的敌人与最左端的敌人的距离, 以及除了左右两端外的敌人的兵团数目, 和我们要消灭的兵团数量.
接下来 n 行每行包含一个整数. 第 i 行, 表示除左右两端外的第 i 个兵团距离最左端兵团的距离, 距离小于 x. 没有两个兵团在同一个位置

Output

输出仅包含一个整数. 表示距最近的敌人的两个兵团间的距离.

Sample

Input

25 5 2
2
14
11
21
17

Output

4

Limitation

对于 10% 的数据, 满足 0 < x ≤ 1000, 0 < n ≤ 10, m ≤ n
对于 50% 的数据, 满足 0 < x ≤ 10000, 0 < n ≤ 1000, m ≤ n
对于 100% 的数据, 满足 0 < x ≤ 109, 0 < n ≤ 50000, m ≤ n
1s, 64000KiB for each test case.

Hint

Source

CDQZ TEST