M. Dimly Lit
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

The mayor is trying to cut costs in the city, and one of his latest ideas is to use less powerful light bulbs in the lampposts. After all, each lamppost is wasting energy if its light bulb illuminates more than necessary! Of course, if the distance between the lampposts were uniform, the calculation would be simple. However, since the mayor also cut costs when placing the lampposts, they are in completely arbitrary positions on the city streets.

However, the mayor knows about economies of scale, so he wants to order all the light bulbs with the same power, the minimum needed to illuminate everything. We define the power of a light bulb as the distance it illuminates to the left and right. Now, the city's electricity department has approached you. Given the positions of the lampposts on the street, what power is needed in the light bulbs to illuminate the entire street?

Input

The first line contains the integers $$$N$$$ $$$(1 \le N \le 2\cdot10^5)$$$, the length of the street in meters, and $$$M$$$ $$$(1 \le M \le N + 1)$$$, the number of lampposts.

Following that, there are $$$M$$$ distinct integers on a single line, the positions of the lampposts $$$P_i$$$ $$$(0 \le P_i \le N)$$$ on the street, in meters, sorted from smallest to largest (i.e., $$$P_i \lt P_j$$$ if $$$i \lt j$$$). The length of the mayor's city streets starts at 0 and ends at $$$N$$$.

Output

Print a single integer, the power that the light bulbs in the lampposts must have to illuminate the entire street.

Examples
Input
20 5
1 5 9 15 18
Output
3
Input
5 1
1
Output
4
Input
10 2
2 9
Output
4