E-一步两步是魔鬼的步伐
题号:NC200610
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

数据已修改,比赛时的所有提交已经进行了rejudge。
    假面骑士要过河,恰好河的两岸间有N(0 ≤ N ≤ 50,000)块石头在同一条直线上。他已经知道了河的宽度L(1 ≤ L ≤ 1,000,000,000)和每一块石头离假面骑士所在河岸的距离Di(0 < Di < L),石头不会发生重叠。
    可是假面骑士在与怪物的激烈战斗之后,留下了后遗症。他不能忍受跨越任何一块石头,所以他只能一块一块地按距离顺序踩着石头过河。皮卡丘是他的好朋友,皮卡丘为了帮助他,已经使用十万伏特去掉了M (0 ≤ M ≤ N)块石头,不过皮卡丘没有告诉假面骑士到底去掉了哪些位置的石头。
    假面骑士想知道在过河的过程中,他需要跨越的最小距离最大可能是多少。

输入描述:

有多组测试,保证 ∑N≤5*106
每个测试的第一行是河的宽度L,石头总数N,被消灭石头的个数M
第二行有N个数,表示每块石头到假面骑士所在河岸的距离

输出描述:

输出在所有可能的情况下,需要跨越的最小距离最大可能是多少
示例1

输入

复制
5 2 1
3 4
25 5 2
2 14 11 21 17

输出

复制
2
4

说明

第一组样例中,河的宽度为5,距河岸3、4的两个位置有石头。若皮卡丘没有消灭石头,那么假面骑士一定会依次从左岸0到3到4再到右岸5这样过河。
已知皮卡丘消灭了1个石头,
如果去掉在位置3的石头,那么假面骑士会依次从0到4到5,此时过河的过程中最小距离为5-4=1。
但如果去掉了在位置4的石头,那么假面骑士会依次从0到3到5,此时过河的过程中最小距离为5-3=2。
所以第一组样例的答案应该为2。