Maximize Minimum Distance for Seating Guests

You are given n seats arranged in a straight line, labeled from 0 to n-1, and k guests. Your task is to seat all the guests such that the minimum distance between any two guests is maximized. In other words, determine the largest possible value d so that it is possible to assign seats to all guests such that the distance between any two seated guests is at least d.

The problem can be formally stated as follows:

Given an integer \( n \) representing the number of seats and a list of guest names of size \( k \), find the maximum integer \( d \) such that the guests can be placed in the seats at positions \( 0, 1, 2, \dots, n-1 \) with a minimum gap of \( d \) between any two guests. Note that if there is only one guest, the answer is \( n-1 \) because no spacing constraint is needed.

Hint: A binary search approach can be utilized due to the monotonicity of the seating condition. For a given potential value \( d \), check if it is possible to seat all guests by iterating through the seats sequentially.

The formula for the condition is given in \( \LaTeX \) as:

[ \text{if } (i - \text{last_position} \ge d) \text{ then place a guest at seat } i. ]

inputFormat

The input is read from standard input and consists of multiple lines:

• The first line contains two integers \( n \) and \( k \), where \( n \) is the total number of seats, and \( k \) is the number of guests.
• The following \( k \) lines each contain a string representing the name of a guest.

Example:

5 3
Alice
Bob
Charlie

outputFormat

Output a single integer representing the maximum minimum distance between any two guests when seated optimally. The output should be written to standard output.

Example:

2

## sample

5 3
Alice
Bob
Charlie

2