Migrated from Lutece 855 分割包围

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

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

Input

第一行包含三个整数，$x,n,m(x \leq 10^9,n \leq 50000,m \leq n)$。表示最右端的敌人与最左端的敌人的距离，以及除了左右两端外的敌人的兵团数目，和我们要消灭的兵团数量。

接下来n行每行包含一个整数。第$i$行，表示除左右两端外的第$i$个兵团距离最左端兵团的距离，距离小于$x$。没有两个兵团在同一个位置

Output

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

Samples

25 5 2
2
14
11
21
17

4

Resources

2014 UESTC Training for Search Algorithm