Minimizing Maximum Hospital Distance

You are given a row of n cities (numbered from 0 to n-1) and you need to build m hospitals in these cities. The cities are arranged in order, and each adjacent pair is at a unit distance apart. Even though a list of integers is provided for each city, it does not affect the computation (its length always equals n).

Your goal is to choose the cities where hospitals will be built so that the maximum distance that any city is from its nearest hospital is minimized.

Formally, let the cities be indexed from 0 to n-1. If hospitals are placed at some cities, then every city has a distance to a hospital equal to the difference in their indices (i.e. the absolute difference). You must determine the minimum possible value of the maximum distance any city has to travel to reach a hospital.

The answer can be expressed using the following binary search approach. Define a function isFeasible(d) which checks if it is possible to cover all cities by placing hospitals such that every city is within an index distance of d from some hospital. Use binary search on d (with \(0 \le d \le n-1\)) to find the minimum feasible d. All formulas including the search range are expressed in \(\LaTeX\) as follows:

\(\text{Initial search range: } d \in [0, n-1]\)

\(\text{Feasibility condition: For every city } i\text{, if } i - \text{lastPlaced} > d \text{, place a new hospital.}\)

inputFormat

The input is given via stdin and consists of two lines:

1. The first line contains two integers n and m, where n is the number of cities and m is the number of hospitals.
2. The second line contains n space-separated integers. These integers represent extra data for each city (for example, population) but are not used in the calculation.

outputFormat

Output a single integer to stdout: the minimum possible value of the maximum distance any city has to travel to reach the nearest hospital.

## sample

5 2
1 2 3 4 5

2