Step

Ο Mirko και ο Slavko άρχισαν να κάνουν μαθήματα /////tap dance. Αυτός ο χορός αποτελείται κυρίως από το χτύπημα στο πάτωμα με ένα ειδικό είδος παπουτσιού. Δεδομένου ότι ο Mirko και ο Slavko μαθαίνουν γρήγορα, αποφάσισαν να φτιάξουν τη δική τους χορογραφία.
Η χορογραφία /////Tap dance μπορεί να περιγραφεί ως μια ακολουθία που αποτελείται από δύο γράμματα, το "L" και το "R". "L" σημαίνει ότι πρέπει να χτυπήσετε το πάτωμα με το αριστερό σας πόδι και "R" με το δεξί σας πόδι. Ο Mirko συνειδητοποίησε ότι τα πιο συναρπαστικά μέρη του tap dancing είναι αυτά στα οποία δεν χρησιμοποιείς το ίδιο πόδι δύο φορές στη σειρά. Όρισε την αξία μιας χορογραφίας ως τη μεγαλύτερη υποακολουθία διαδοχικών στοιχείων που δεν περιέχει δύο διαδοχικά "L" ή "R".
Όπως όλοι γνωρίζουμε, ο σχεδιασμός μιας χορογραφίας μπορεί να είναι πολύ δύσκολος, με πολλές μικρές αλλαγές μέχρι να ολοκληρωθεί. Για κάθε αλλαγή που κάνει ο Slavko, θα ήθελε να γνωρίζει την τρέχουσα χορογραφική αξία. Μια αλλαγή αλλάζει ένα "L" σε "R" και το αντίστροφο. Πριν γίνουν οποιεσδήποτε αλλαγές, η χορογραφία αποτελείται μόνο από τα γράμματα "L".

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει δύο ακέραιους αριθμούς, το μήκος της χορογραφίας ~N\;(1 \leq N \leq 200\,000)~ και τον αριθμό των αλλαγών ~Q(1 \leq Q \leq 200\,000)~.
Κάθε μία από τις επόμενες ~Q~ γραμμές περιέχει έναν ακέραιο που καθορίζει τη θέση που αλλάζουν οι Mirko και Slavko, με σειρά αλλαγών.

Έξοδος

Η έξοδος πρέπει να περιέχει ~Q~ ακέραιους αριθμούς, έναν ανά γραμμή - τις τρέχουσες τιμές της χορογραφίας μετά από κάθε αλλαγή.

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

input

6 2
2
4

output

3
5

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

οι χορογραφιες ειναι: ~LLLLLL \rightarrow L\textbf{R}LLLL \rightarrow LRL\textbf{R}LL~

input

6 5
4
1
1
2
6

output

3
3
3
5
6