Задача 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 проходів |
