#include <bits/stdc++.h>
 
using namespace std;   
 
 bool check(int n, int k, vector<int> &stalls, int mid){
        int lastPosition = stalls[0];
        k--;
        for(int i = 1; i<n; i++){
            if(stalls[i]-lastPosition >=mid){
                k--;
                lastPosition = stalls[i];
            }
            if(k==0) return true;
        }
        return false;
    }
 
    int solve(int n, int k, vector<int> &stalls) {
        sort(stalls.begin(),stalls.end());
        int l = 0, r = 1e9, res = 0;
        while(l<=r){
            int mid = l + (r-l)/2;
            if(check(n, k, stalls, mid)){
                res=mid;
                l=mid+1;
            }else r=mid-1;
        }
        return res;
    }
 
int main() {
    int n = 5, k =3;
	vector<int>stalls={1,2,4,8,9};
    cout<<solve(n,k,stalls)<<endl;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOyAgIAoKIGJvb2wgY2hlY2soaW50IG4sIGludCBrLCB2ZWN0b3I8aW50PiAmc3RhbGxzLCBpbnQgbWlkKXsKICAgICAgICBpbnQgbGFzdFBvc2l0aW9uID0gc3RhbGxzWzBdOwogICAgICAgIGstLTsKICAgICAgICBmb3IoaW50IGkgPSAxOyBpPG47IGkrKyl7CiAgICAgICAgICAgIGlmKHN0YWxsc1tpXS1sYXN0UG9zaXRpb24gPj1taWQpewogICAgICAgICAgICAgICAgay0tOwogICAgICAgICAgICAgICAgbGFzdFBvc2l0aW9uID0gc3RhbGxzW2ldOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGlmKGs9PTApIHJldHVybiB0cnVlOwogICAgICAgIH0KICAgICAgICByZXR1cm4gZmFsc2U7CiAgICB9CgogICAgaW50IHNvbHZlKGludCBuLCBpbnQgaywgdmVjdG9yPGludD4gJnN0YWxscykgewogICAgICAgIHNvcnQoc3RhbGxzLmJlZ2luKCksc3RhbGxzLmVuZCgpKTsKICAgICAgICBpbnQgbCA9IDAsIHIgPSAxZTksIHJlcyA9IDA7CiAgICAgICAgd2hpbGUobDw9cil7CiAgICAgICAgICAgIGludCBtaWQgPSBsICsgKHItbCkvMjsKICAgICAgICAgICAgaWYoY2hlY2sobiwgaywgc3RhbGxzLCBtaWQpKXsKICAgICAgICAgICAgICAgIHJlcz1taWQ7CiAgICAgICAgICAgICAgICBsPW1pZCsxOwogICAgICAgICAgICB9ZWxzZSByPW1pZC0xOwogICAgICAgIH0KICAgICAgICByZXR1cm4gcmVzOwogICAgfQoKaW50IG1haW4oKSB7CiAgICBpbnQgbiA9IDUsIGsgPTM7Cgl2ZWN0b3I8aW50PnN0YWxscz17MSwyLDQsOCw5fTsKICAgIGNvdXQ8PHNvbHZlKG4sayxzdGFsbHMpPDxlbmRsOwp9