Tamnica

Ο γενναίος σερ Ρόμπιν φυλακίστηκε στο μπουντρούμι από τον κακό βασιλιά. Το μπουντρούμι αποτελείται από ένα άπειρο πλήθος δωματίων σε σχήμα κύβου με μεγάλους πέτρινους τοίχους. Τα δωμάτια συνδέονται με περάσματα έτσι ώστε ολόκληρο το μπουντρούμι, όταν το δει κανείς από ψηλά, μοιάζει με σπείρα. Τα δωμάτια αριθμούνται ως εξής:

Μετά από έναν μεγάλο σεισμό, μερικά από τα τείχη κατέρρευσαν και δημιουργήθηκαν νέα περάσματα μεταξύ γειτονικών δωματιών.
Ο Sir Robin βρίσκεται αρχικά στο δωμάτιο ~1~. Ο Sir Robin γνωρίζει ότι η έξοδος από το μπουντρούμι βρίσκεται στο δωμάτιο ~N~, και θέλει να δραπετεύσει ενώ όλων η προσοχή έχει αποσπαστεί από τον σεισμό. Επειδή ο κακός δράκος φυλάει το μπουντρούμι, ο Σερ Ρόμπιν θέλει να χρησιμοποιήσει την πιο γρήγορη έξοδο από το μπουντρούμι.
Γράψτε ένα πρόγραμμα που, δεδομένης της θέσης της εξόδου ~N~ και της λίστας των νέων περασμάτων, να καθορίζει το μικρότερο αριθμό περασμάτων που πρέπει να περάσει ο Σερ Ρόμπιν πριν μπορέσει να βγει από το μπουντρούμι.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει έναν ακέραιο αριθμό ~N~ ~(1 \le N \le 10^{15})~, το δωμάτιο στο οποίο βρίσκεται η έξοδος.
Η δεύτερη γραμμή εισόδου περιέχει έναν ακέραιο αριθμό ~K~ ~(1 \le K \le 100\, 000)~, τον αριθμό των νέων περασμάτων.
Κάθε μία από τις ακόλουθες ~K~ γραμμές περιέχει έναν ακέραιο ~B~ ~(4 \le B \le 10^{15})~, που σημαίνει ότι ένα νέο πέρασμα τώρα συνδέει τις γειτονικές αίθουσες ~A~ και ~B~, όπου ~A<B~. Ο αριθμός ~A~ δεν δίνεται αναλυτικά, αλλά μπορεί να είναι προσδιοριστεί μοναδικά από το ~B~ (για παράδειγμα, αν το ~B~ είναι ~20~, τότε το ~A~ πρέπει να είναι ~7~). Επίσης, κάποια δωμάτια δεν μπορούν ποτέ να είναι το δωμάτιο ~B~ (δωμάτια ~2,\,3,\,5,\,7,\,10,\,13~ κ.λ.π.).

Έξοδος

Η έξοδος πρέπει να αποτελείται από έναν μόνο ακέραιο αριθμό, τον ελάχιστο αριθμό περασμάτων που πρέπει να περάσει ο Sir Robin προτού μπορέσει να βγει από το μπουντρούμι.

Βαθμολόγηση

Σε ορισμένες δοκιαστικές περιπτώσεις, συνολικής αξίας ~50~ πόντων, το ~N~ θα είναι το πολύ ~10^6~.

Παραδείγματα

input

31
9
15
25
30
6
9
19
24
27
4

output

6

Επεξήγηση του 1ου παραδείγματος:

Αυτό είναι το διάγραμμα του μπουντρουμιού μετά το σεισμό:

Ο Sir Robin μπορεί να χρησιμοποιήσει τη διαδρομή ~1-4-15-14-13-30-31~, χρησιμοποιώντας μόνο ~6~ περάσματα για να βγει από το μπουντρούμι.

input

10000
5
52
4
9
25
27

output

9953