Giáo sư X đang sáng tác một tiết mục “VŨ ĐIỆU GÓT GIÀY” và mời các sinh viên làm vũ công biểu diễn thử trong quá trình sáng tác. Vũ điệu bao gồm một số nhịp đập chân xuống sàn nhảy bằng một loại giày đặc biệt. Một vũ điệu có thể coi là một dãy các ký tự L và R. Ký tự L có nghĩa là vũ công sẽ dùng chân trái để đập xuống sàn còn ký tự R có nghĩa là vũ công sẽ dùng chân phải để đập xuống sàn.

Các vũ công nhận ra rằng phần khó trong một điệu nhảy phải là một đoạn các ký tự liên tiếp sao cho khi nhảy đoạn đó thì vũ công sẽ phải nhảy bằng một chân. Ta định nghĩa "độ khó của vũ điệu bằng độ dài của dãy ký tự liên tiếp giống nhau dài nhất".

Bắt đầu với một vũ điệu gồm n ký tự L, tại mỗi bước giáo sư X chọn một ký tự bất kỳ trong vũ điệu, nếu ký tự đó là L sẽ được đổi thành R và ngược lại, ký tự R sẽ được đổi thành L.

Yêu cầu: Cho ~q~ phép đổi ký tự mà giáo sư X thực hiện, sau mỗi phép đổi ký tự, hãy giúp các vũ công xác định độ khó của vũ điệu.

Input

• Dòng 1 chứa hai số nguyên dương ~n ≤ 10^9, q ≤ 10^5~
• ~q~ dòng tiếp theo mỗi dòng chứa một vị trí mà Slavko đổi ký tự tại vị trí đó

Output

• Gồm ~q~ dòng, mỗi dòng ghi độ khó của điệu nhảy sau mỗi phép đổi của Slavko.

Sample

Input #1

6 3
2
4
3

Output #1

4
2
3

Problem source: Kc97ble - Free Contest 18