거리 개발

ICPC 거리는 아직 개발되지 않은 구역이다. 곧 대규모 개발 계획이 시작될 예정이다. 개발을 시작하기 전에 원격 조종 로봇 $n$대가 거리를 따라 놓인 중요 지점 $n$곳에서 정보를 수집한다. 각 지점에는 로봇이 한 대씩 놓인다. 목표는 수집한 정보를 모두 한 로봇에 모아 가장 효율적인 개발 방법을 찾는 것이다.

거리는 양의 정수 $L$에 대한 구간 $[0, L]$이다. 중요 지점 $p_1, p_2, \dots, p_n$은 양 끝점을 포함한 구간 위의 정수이다. 즉 $p_1 = 0$, $p_n = L$이다. 처음에 각 로봇은 중요 지점 하나에 있으며, 그 지점의 정보를 이미 가지고 있다. 지점마다 로봇이 정확히 한 대이므로 $n$은 로봇의 수이기도 하다. $2 \le n \le L + 1$이다.

1. 로봇은 왼쪽이나 오른쪽으로 자유롭게 움직일 수 있다. 이동한 거리 1마다 방향과 관계없이 배터리를 1 소모한다. 모든 로봇은 같은 배터리 용량인 정수 $P$를 가지며, 정수 단위의 거리만 움직인다.
2. 두 대 이상의 로봇이 정수 위치에서 만나면 서로의 정보를 합칠 수 있다. 예를 들어 $p_1$과 $p_2$의 정보를 가진 로봇이 $p_3$과 $p_4$의 정보를 가진 로봇과 만나면, 두 로봇 모두 $p_1$, $p_2$, $p_3$, $p_4$의 정보를 갖게 된다.
3. 배터리는 이동에만 쓰인다. 방향을 바꾸거나 정보를 합칠 때는 배터리를 쓰지 않는다.
4. 모든 이동이 끝난 뒤 적어도 한 로봇이 $p_1, p_2, \dots, p_n$의 정보를 모두 가져야 한다.

그림은 $L = 10$, $n = 4$인 예시이다. 로봇 R1, R2, R3, R4는 각각 $p_1 = 0$, $p_2 = 3$, $p_3 = 7$, $p_4 = 10$에서 출발한다. 배터리 용량이 $P = 3$이면 다음 순서로 진행할 수 있다. 로봇 1이 $p_2$로 이동해 로봇 1과 2가 정보를 합친다. 로봇 4가 $p_3$으로 이동해 로봇 3과 4가 정보를 합친다. 로봇 2는 오른쪽으로 2만큼, 로봇 3은 왼쪽으로 2만큼 움직여 위치 5에서 정보를 합친다. 이후 로봇 2와 3은 네 지점의 정보를 모두 갖는다.

첫 줄에 양의 정수 $L$과 $n$이 주어진다 ($1 \le L \le 10^6$, $2 \le n \le L + 1$). 둘째 줄에는 로봇의 초기 위치인 $0$부터 $L$까지의 서로 다른 정수 $n$개가 증가하는 순서로 주어진다. 첫 값은 $0$이고 마지막 값은 $L$이다.

한 줄에 정수 하나를 출력한다. 적어도 한 로봇이 모든 중요 지점의 정보를 가질 수 있는 최소 배터리 용량 $P$이다.