Bình đ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.

Sau khi Bình nhảy thử thì 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. Yên nghĩ ra rằng độ 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\).

Câu đố cho các bạn như sau: Ban đầu Bình sẽ 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, các bạn 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 ≤ N ≤ 200.000)\) và số lần thay đổi là \(Q (1 ≤ Q ≤ 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

7 5
2
4
4
4
6

Sample Output

3
5
3
5
7