Street Development

문제

ICPC street is currently an undeveloped area, with a large-scale development plan scheduled soon. Before starting the development, information about $nn$ important points along the street will be collected using $nn$ remote-controlled robots, with each robot collecting information from one of these important points. Now, the goal is to combine all the collected information into a single robot to find the most efficient development approach. To combine the information, the robots can move towards left or right and combine the information that they have from other robots. Also, each robot is powered by its own battery, and all the robots are equipped with identical batteries. Specifically, let $p_1,p_2,\dots ,p_{n}p\_1,\; p\_2,\; \backslash dots\; ,\; p\_n$ represent the positions of the important points where the robots collect information, arranged from left to right. Then the requirements are as follows:

1. The ICPC street is considered as a one-dimensional interval $[0,L][0,\; L]$ with a positive integer $LL$. The important points $p_1,p_2,\dots ,p_{n}p\_1,\; p\_2,\; \backslash dots\; ,\; p\_n$ are always represented as integers on the interval, including two endpoints of the interval. That is, $p_1=0p\_1\; =\; 0$ and $p_n=Lp\_n\; =\; L$. Initially, each robot is positioned at one of the important points, so it has the information of the important point before beginning to move. Note that there is exactly one robot at each of these points initially, which means $nn$ is also the number of robots, and always at least $22$ and at most $L+1L\; +\; 1$.
2. For combining the information from other robots, robots can move freely to the left or right, consuming $11$ unit of battery for $11$ unit of distance traveled, regardless of direction. All robots are equipped with the same battery capacity with integer $PP$, and move only in integer units of distance.
3. When two or more robots meet at the integer position on the street, they can combine each other's information. For example, if a robot with information about $p_{1}p\_1$ and $p_{2}p\_2$ encounters with a robot with information about $p_{3}p\_3$ and $p_{4}p\_4$, both robots will then have information about the positions $p_{1}p\_1$, $p_{2}p\_2$, $p_{3}p\_3$, and $p_{4}p\_4$.
4. Robots consume the battery only for movement. Therefore, they do not use the battery when changing direction or when combining the information from other robots.
5. After all movements, at least one robot must have information about all the positions $p_1,p_2,\dots ,p_{n}p\_1,\; p\_2,\; \backslash dots\; ,\; p\_n$.

For example, the figure above shows an example with $L=10L\; =\; 10$, $n=4n\; =\; 4$, and Robots $11$, $22$, $33$, and $44$ (R1, R2, R3, R4 in the figure) collect information (and are initially positioned) at $p_1=0p\_1\; =\; 0$, $p_2=3p\_2\; =\; 3$, $p_3=7p\_3\; =\; 7$, and $p_4=10p\_4\; =\; 10$, respectively. Then the following sequence of steps can be performed with a battery capacity of $P=3P\; =\; 3$:

1. Robot $11$ moves to $p_{2}p\_2$, and Robots $11$ and $22$ combine each other’s information.
2. Robot $44$ moves to $p_{3}p\_3$, and Robots $33$ and $44$ combine each other’s information.
3. Robot $22$ moves $22$ units to the right, Robot $33$ moves $22$ units to the left, and they combine each other’s information at the position $55$ on the street.

Then after completing the process, Robots $22$ and $33$ will have information about all the positions $p_{1}p\_1$, $p_{2}p\_2$, $p_{3}p\_3$, and $p_{4}p\_4$.

Since the battery is much more expensive than the other parts of robot, it is important to determine the minimum battery capacity required for each robot for efficient data collection. Given $LL$, $nn$, and the positions of the important points $p_1,p_2,\dots ,p_{n}p\_1,\; p\_2,\; \backslash dots\; ,\; p\_n$, write a program to calculate the minimum battery capacity $PP$ required for at least one robot to have information about all the points.

입력

Your program is to read from standard input. The input starts with a line containing two positive integers, $LL$ and $nn$ (1 ≤ L ≤ 10^6 , 2 ≤ n ≤ L + 1), where $nn$ is the number of robots and important points on the street and $LL$ is the position of the right endpoint of the street. In the following line, $nn$ distinct integers between $00$ and $LL$ that represent the positions of important points of the street (the initial positions of the robots) are given in increasing order, where the first integer is $00$ and the last one is $LL$.

출력

Your program is to write to standard output. Print exactly one line. The line should contain a single integer that represents the minimum battery capacity $PP$ required for at least one robot to have information about all the important points.

10 4
0 3 7 10

3

100 5
0 97 98 99 100

49

1 2
0 1

1