我们假设要求最小的区间是x，当前的条件下能否满足这个最小区间呢？我们知道，如果能满足最小区间x，那么x1<x的x1也都可以满足。所以求最大的x，一定在一个分界点，所有小于x的最小区间要求都可以满足，所有大于x的最小区间要求都不能满足，这样可以用二分法在解空间里面找到这个分界。

写一个C(x)函数，传入的x是最小区间的要求，判断能否满足这个要求。
使用二分法，如果mid能满足要求，那么临界点一定在mid-ub，否则临界点就在lb-mid。

/**
 * 最大化最小值
 */
#include <iostream>
#include <stdio.h>
#include <algorithm>
#define MAX_N 50000
#define INF 9999999999
void solve(void);
bool C(unsigned long x);
unsigned long L,N,M;
//l 长度1-1,000,000,000  
//N 石头数量
//M 可移除的石头数量
unsigned long D[MAX_N+100];


using namespace std;
int main(void)
{
    cin>>L>>N>>M;
    for(int i = 1; i <= N;i++)
    {
        scanf("%lu",D+i);
    }
    D[N+1] = L;
    sort(D,D+N+2);
    solve();
    return 0;
}
void solve(void)
{
    if(N==0&&M==0) cout<<L<<endl;
    else
    {
        unsigned long ub=INF,lb=0;/*解区间，尽量让解更大*/
        while(ub-lb>1)
        {
            unsigned long mid = (ub+lb)/2;
            // printf("%lu,%lu,%lu\n",lb,ub,mid);
            if(C(mid)) lb  = mid;
            else ub = mid;

        }
        cout<<lb;
    }
}
/**
 * 计算是否可以满足最低间隔是x的要求
 * 
 * */
bool C(unsigned long x)
{
    //这里的算法是这样的，计算出来能达到x间距所需的最少的移走石头数量，然后和M比较，如果<=M，就可以，否则据不可
    //如何计算所需的最少移走石头数量呢？移走的石头最少，区间数量就越多，计算最多的区间数量即可。
    //如何计算最多的区间数呢，从start开始，计算到下一个石头的距离，如果>=x，那么就表示这个区间可以保留，就保留住
    //如果实在是不能保留这个区间，就找下一个石头，和下一个符合要求的石头组成一个区间
    //只要能满足区间>x就保留这个区间，满足区间数量最多，移动石头最少
    unsigned long st = 0,ed = 1,sum=0;//初始区间
    while(ed<=(N+1))
    {
        if(D[ed]-D[st] >= x)
        {
            // printf("%lu 到 %lu 符合要求\n",D[st],D[ed]);
            st = ed;
            sum++;
        }
        ed++;
    }
    //现在得到的区间最多数目sum，这样就能求出来最少需要去掉几个石头
    if( (N+1-sum) > M) return false;
    return true;
}