Фрагмент екранаЗадача Hoard. Пираты спрятали клад в подземном лабиринте, который состоит из бесконечного количества комнат с каменными стенами. Комнаты имеют номера и соединены переходами, так что все подземелья, если смотреть сверху, выглядит как спираль. Комнаты пронумерованы, как на рисунке. После большого землетрясения некоторые стены разрушились, а между смежными комнатами образовались новые проходы. Вход в лабиринт находится в комнате 1 Кладоискатель знает, что сокровище находится в комнате N. Напишите программу, которая, учитывая расположение клада N и список новых переходов, определяет наименьшее количество переходов, через которые должен пройти искатель, пока доберется до сокровища.

Технические условия. Программа Hoard читает с устройства стандартного ввода в первой строке целое число N (1 ≤ N ≤ 1015) - номер комнаты, в которой расположен сокровище, во второй строке - целое число K (1 ≤ K ≤ 100 000), количество новых переходов . Каждый из следующих K строк содержит одно целое число B (4 ≤ B ≤ 1015), что означает, что теперь новый переход объединяет смежные помещения A и B, где A<B. Номер А не задано явным образом, но его можно однозначно определить по  B (например, если B равно 20, то A должно быть 7). Кроме того, в некоторые комнаты никогда не могут быть номером В (номера 2, 3, 5, 7, 10, 13 и т.д.). Программа выводит на устройство стандартного вывода единственное целое число - наименьшее количество переходов, через которые искатель должен пройти, прежде чем он может добраться до сокровища.

Примеры

Ввод

31

 9

15

25

30

6

9

19

24

27

4

 

Вывод

6

Ввод

10000

5

52

4

9

25

27

 

Вывод

9953

Фрагмент екрана

 

 

 

Пояснение к первому примеру:

1-4-15-14-13-30-31

К сокровищу можно добраться,

пройдя 6 проходов

 

© LIKT 1998-2018