무한한 격자들로 구성된 달팽이 미로가 있다. 이 미로의 각 격자는 나선형으로 1에서부터 순서대로 매겨진다. 이웃한 두 수가 있는 두 격자를 제외하곤, 한 변을 공유하는 두 격자 사이에는 벽으로 막혀 있어서 통행이 불가능하다.

이 미로에 미르코가 1번 격자에 갇혀 있고, 탈출구는 N번 격자에 있다. 미르코가 이웃한 격자로 이동하는 시간은 1이다. 미르코는 최단 시간으로 이 미로를 탈출하려고 한다.

그런데 예전에 슬라브코가 이 미로를 탈출하면서 K개의 벽을 부수고 갔다. 따라서 미르코는 슬라브코가 부쉈던 벽을 사이에 둔 두 격자 사이에는 통행이 가능하다.

미로의 정보와 슬라브코가 부순 벽들의 정보가 주어질 때 미르코가 미로를 탈출할 때 걸리는 최단 시간을 구하는 프로그램을 작성하여라.

입력

• 첫 번째 줄에는 탈출구가 있는 격자의 번호 N이 주어진다. (1 ≤ N ≤ 10^15)
• 두 번째 줄에는 슬라브코가 부순 벽의 수 K가 주어진다. (1 ≤ K ≤ 100,000)
• 세 번째 줄부터 K개의 줄에는 B가 주어진다. (4 ≤ B ≤ 10^15) 이는 슬라브코가 격자 A와 격자 B 사이의 벽을 부쉈다는 것을 의미한다. (단, A < B) A가 주어지지 않았지만, B에 의해서 유일하게 결정된다. (B가 20이면 A로 가능한 값은 7밖에 없다)

출력

입출력 예

입력 예 1

31
9
15
25
30
6
9
19
24
27
4

출력 예 1

6

입력 예 1

10000
5
52
4
9
25
27

출력 예 1

9953

입력 예 1 설명

미르코가 1-4-15-14-13-30-31을 통해 격자를 이동하면 6의 시간이 걸리고, 이것이 최단 시간이다.

출처:2007-2008/coci/
번역:functionx