URI Online Judge | 3079

Illuminated Street

By Guilherme Londe, PUC Goiás BR Brazil

Timelimit: 2

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:

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 Ai  and Ai+1 - 1, inclusive, where 1 ≤ i < N, and the last house means the segment between AN 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 ≤ 103, 2 ≤ M ≤ 105), which describes the number of houses and the length of the street, respectively. The second line contains N integers Ai  (0 ≤ Ai < MAi  < Ai+1 for all 1 ≤ i < N), which represents the coordinates of the beginning of each house in the street. It is guaranteed that A1 = 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
0 12 15


5 20
0 4 8 9 12


6 121
0 29 46 55 81 114