#include <stdio.h>

int main() {
    int house[5] = {1, 2, 4, 8, 9};
    int c = 3;
    int low,high,mid;
    low = 1;
    high = 8;
    int result = 0;

    while(low <= high){
    mid = (low + high) / 2;
    int count = 1;
    int last = house[0];

        for(int i = 1; i < 5; i++){
            if (house[i] - last >= mid){
                count++;
                last = house[i];
            }
        }
    
        if(count >= c){
            result = mid;
            low = mid + 1;
        }
        else{
            high = mid - 1;
        }
}
    printf("%d",result);   
}