Bình và Yên là bí thư và phó bí thư đoàn trường chuyên Nguyễn Trãi. Trong buổi giao lưu của các học sinh, Bình sẽ đi một đôi giày đặc biệt để nhảy, mỗi chiếc giày khi gõ nhịp trên sàn sân khấu sẽ tạo ra âm thanh khác nhau.

Điệu nhảy của Bình được mô tả bằng một chuỗi gồm các ký tự là "L" hoặc "R", trong đó "L" là mô tả Bình gõ nhịp lên sàn bằng chân trái; "R" là mô tả Bình gõ nhịp lên sàn bằng chân phải. Yên thấy âm thanh của đôi giày phát ra khi nhảy sẽ rất hay khi Bình không gõ nhịp lên sàn bằng hai nhịp liên tiếp của một chân. Độ hay của điệu nhảy chính là độ dài của dãy con dài nhất của dãy ký tự liên tiếp không chứa hai ký tự giống nhau liên tiếp là "L" hoặc "R".

Ban đầu Bình dự kiến điệu nhảy chỉ gồm các ký tự "L". Khi Bình thực hiện nhảy trên sân khấu thì Bình tự sáng tạo thay đổi nhịp chân từ "L" thành "R" và ngược lại.

Yêu cầu: Mỗi lần thay đổi nhịp chân của Bình, hãy cho biết độ hay của điệu nhảy hiện tại là bao nhiêu.

Input

• Dòng đầu tiên chứa hai số nguyên, độ dài của điệu nhảy là ~N~ (~1 \le N \le 200.000~) và số lần thay đổi là ~Q~ (~1 \le Q \le 200.000~).
• ~Q~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ghi rõ vị trí mà Bình đang thay đổi, trong thứ tự thay đổi.

Output

• ~Q~ dòng, mỗi dòng chứa một số nguyên dương là độ hay của điệu nhảy ứng với mỗi bước thay đổi trong input.

Sample Input 1

7 5
2
4
4
4
6

Sample Output 1

3
5
3
5
7