题目描述

FJ 让农场的 \(N\) 头奶牛站在一条长度为 \(L\) 的道路上的不同位置（保证 \(0\) 和 \(L\) 这两个位置必然有奶牛占据）。有的奶牛相邻的奶牛之间间隔的比较远，奶牛就会不开心，我们用奶牛间的最大间距来表示不开心指数。现在 FJ 又找了 \(K\) 头奶牛，FJ 最多可以把 \(k\) 头奶牛插入到道路中去帮助减小奶牛的不开心指数。请你帮忙计算奶牛的不开心指数最小是多少。

格式

输入格式

输入第 \(1\) 行包含 \(3\) 个整数 \(L,N,K\)；含义如题意所述。

输入第 \(2\) 行一共 \(N\) 个整数，表示 \(N\) 头奶牛的位置（位置一定介于 \(0\) 到 \(L\) 之间）。

输出格式

输出 \(1\) 行一个整数，表示把 \(k\) 头奶牛放入道路中后，此时的最小不开心指数。

样例1

样例输入1

6614 9 0
0 6532 1137 5755 1109 1099 2544 2441 6614

样例输出1

3211

限制

对于 \(50\%\) 的数据，\(2 ≤ N ≤100，0 ≤K ≤100 0<L≤10000\)；

对于 \(100\%\) 的数据，\(2 ≤ N ≤100000，0 ≤K ≤100000 0<L≤10^{7}\)；

来源

地址：\(\text{Online~Judge}\)
作者：\(hoogy\)
模拟赛\(T4\)