#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