Street Development

ICPC street is still an undeveloped area, and a large-scale development plan is scheduled to start soon. Before development begins, $n$ remote-controlled robots collect information from $n$ important points along the street, one robot per point. The goal is to combine all the collected information into a single robot so that the most efficient development approach can be found.

The street is the interval $[0, L]$ for a positive integer $L$. The important points $p_1, p_2, \dots, p_n$ are integers on the interval, including both endpoints. That is, $p_1 = 0$ and $p_n = L$. At the start, each robot stands at one important point and already has that point's information. There is exactly one robot per point, so $n$ is also the number of robots. $2 \le n \le L + 1$.

1. Robots can move left or right freely. Each unit of distance traveled costs 1 unit of battery, in either direction. All robots have the same battery capacity, an integer $P$, and move only in integer units of distance.
2. When two or more robots meet at an integer position, they combine each other's information. For example, if a robot holding the information of $p_1$ and $p_2$ meets a robot holding the information of $p_3$ and $p_4$, both robots then have the information of $p_1$, $p_2$, $p_3$, and $p_4$.
3. Battery is used only for movement. Changing direction and combining information cost no battery.
4. After all movements, at least one robot must have the information of all of $p_1, p_2, \dots, p_n$.

The figure shows an example with $L = 10$ and $n = 4$. Robots R1, R2, R3, and R4 start at $p_1 = 0$, $p_2 = 3$, $p_3 = 7$, and $p_4 = 10$. With battery capacity $P = 3$, the following steps can be performed. Robot 1 moves to $p_2$, and robots 1 and 2 combine their information. Robot 4 moves to $p_3$, and robots 3 and 4 combine their information. Robot 2 moves 2 units to the right, robot 3 moves 2 units to the left, and they combine their information at position 5. Afterward, robots 2 and 3 have the information of all four points.

The first line contains two positive integers $L$ and $n$ ($1 \le L \le 10^6$, $2 \le n \le L + 1$). The second line contains $n$ distinct integers between $0$ and $L$ in increasing order, which are the initial positions of the robots. The first integer is $0$ and the last one is $L$.

Print one line containing a single integer: the minimum battery capacity $P$ that lets at least one robot have the information of all important points.