By Guilherme Londe, PUC Goiás Brazil
After many complaints on city hall, residents of a specific street will finally have their houses illuminated. To make it possible will be necessary to build a pole network on this street obeying the following constraints:
any two adjacent poles have a distance k between them;
there should be at least one pole in front of each house.
The street has N houses and is considered a strait line. A house is represented by a segment of the street and a pole is said to be in front of this house if it is inside this segment. The i-th house means the segment between A_{i} and A_{i}_{+1} - 1, inclusive, where 1 ≤ i < N, and the last house means the segment between A_{N} and M, inclusive.
The city mayor intends to minimize the number of poles that should be installed by maximizing the distance k. Write a program that finds the biggest distance k that satisfies the above constraints.
The first line of the input contains two integers N and M (2 ≤ N ≤ 10^{3},^{ }2 ≤ M ≤ 10^{5}), which describes the number of houses and the length of the street, respectively. The second line contains N integers A_{i} (0 ≤ A_{i} < M; A_{i} < A_{i}_{+1} for all 1 ≤ i < N), which represents the coordinates of the beginning of each house in the street. It is guaranteed that A_{1} = 0.
The output contains just one line with an integer k, that means the biggest possible distance between two adjacent poles obeying the above constraints.
Input Samples | Output Samples |
3 26 |
13 |
5 20 |
3 |
6 121 |
23 |