던전 탈출

용감한 로빈 경은 사악한 왕에게 붙잡혀 던전에 갇혔다. 던전에는 두꺼운 돌벽으로 둘러싸인 정육면체 모양의 방이 무한히 많다. 연속한 번호의 방들은 통로로 이어져 있으며, 위에서 내려다보면 방의 배치는 다음과 같은 정사각형 나선 모양이다.

큰 지진이 난 뒤 일부 벽이 무너져, 원래는 벽으로 막혀 있던 서로 인접한 방 사이에 새 통로가 생겼다.

로빈 경은 처음에 1번 방에 있다. 출구는 N번 방에 있다. 던전은 용이 지키고 있으므로, 로빈 경은 가능한 한 적은 수의 통로를 지나 출구에 도착하려고 한다.

출구가 있는 방 N과 새로 생긴 통로들의 정보가 주어질 때, 로빈 경이 출구까지 가기 위해 지나야 하는 통로 수의 최솟값을 구하라.

첫째 줄에 출구가 있는 방 번호 N (1 <= N <= 10^15)이 주어진다.

둘째 줄에 새로 생긴 통로의 수 K (1 <= K <= 100000)가 주어진다.

다음 K개의 줄에는 정수 B (4 <= B <= 10^15)가 하나씩 주어진다. 이는 서로 인접한 두 방 A와 B 사이에 새 통로가 생겼다는 뜻이며, A < B이다. A는 입력으로 주어지지 않지만 B로부터 유일하게 결정된다. 예를 들어 B가 20이면 A는 7이다. 2, 3, 5, 7, 10, 13처럼 B로 등장할 수 없는 방도 있다.

로빈 경이 출구까지 가기 위해 지나야 하는 통로 수의 최솟값을 나타내는 정수 하나를 출력한다.

첫 번째 공개 테스트에서 지진 이후 던전의 모습은 다음과 같다.

최단 경로 중 하나는 1-4-15-14-13-30-31이며, 총 6개의 통로를 지난다.