Croatian Olympiad in Informatics 2008

Task TAMNICA

Brave Sir Robin has been thrown in the dungeon by the evil king. The dungeon consists of an infinite number of cube-shaped 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:

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.

Input

The first line of input contains an integer N (1 ≤ N ≤ 10¹⁵), the room in which the exit is located.

The second line of input contains an integer K (1 ≤ K ≤ 100 000), the number of new passages.

Each of the following K lines contains one integer B (4 ≤ B ≤ 10¹⁵), meaning that a new passage now connects adjacent rooms A and B, where A<B. The number A is not given explicitly, but it can be 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

Output should consist of a single integer, the smallest number of passages that Sir Robin must go through before he can exit the dungeon.

Scoring

In a number of test cases, worth a total of 50 points, N will be at most 10⁶.

Examples

31
9
15
25
30
6
9
19
24
27
4

6

10000
5
52
4
9
25
27

9953

Clarification of example 1: This is the layout of the dungeon after the earthquake:

Mirko can use the route 1-4-15-14-13-30-31, using only 6 hallways to exit the dungeon.

All Submissions
Best Solutions

Point Value: 25 (partial)
Time Limit: 1.00s
Memory Limit: 64M
Added: Aug 12, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)