레이팅 미적용Brave Sir Robin has been thrown in the dungeon by the evil king. The dungeon consists of an infinite
number of cu\(be-sh\)aped rooms with big stone walls. Rooms are connected by passages so that the
entire dungeon, when viewed from above, looks like a spiral. The rooms are numbered as follows:
...
35
34
33
32
31
17
16
15
14
13
30
18
5
4
3
12
29
19
6
1
2
11
28
20
7
8
9
10
27
21
22
23
24
25
26
After a big earthquake some of the walls collapsed, and new passages were formed between adjacent
rooms.
Sir Robin is initially in room 1. Sir Robin knows that the exit from the dungeon is located in room N,
and wants to escape while everyone is distracted by the earthquake. Because the evil dragon is guarding
the dungeon, Sir Robin wants to use the fastest way out of the dungeon.
Write a program that, given the location of the exit N and the list of new passages, determines the
smallest number of passages that Sir Robin must go through before he can exit the dungeon.
In a number of test cases, worth a total of 50 points, N will be at most \(10^{6}\).
The first line of input contains an integer N (\(1 \le N \le 10^{15}\)), the room in which the exit is located.
The second line of input contains an integer K (\(1 \le K \le 100\,000\)), the number of new passages.
Each of the following K lines contains one integer B (\(4 \le B \le 10^{15}\)), meaning that a new passage now
connects adjacent rooms A and B, where \(A
uniquely determined from B (for example, if B is 20, then A must be 7). Also, some rooms can never
be room B (rooms 2, 3, 5, 7, 10, 13 etc.).
Output should consist of a single integer, the smallest number of passages that Sir Robin must go
through before he can exit the dungeon.
31
9
15
25
30
6
9
19
24
27
4610000
5
52
4
9
25
279953Clarification of first example. This is the layout of the dungeon after the earthquake:
...
35
34
33
32
31
17
16
15
14
13
30
18
5
4
3
12
29
19
6
1
2
11
28
20
7
8
9
10
27
21
22
23
24
25
26
Mirko can use the route 1-4-15-14-13-30-31, using only 6 hallways to exit the dungeon.