#1442. STEP - Điệu nhảy

Giáo sư đ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 nhảy bằng một chân (lò cò). Một vũ điệu có thể coi là một dãy các ký tự và . Ký tự có nghĩa là vũ công sẽ phải nhảy bằng chân trái còn ký tự có nghĩa là vũ công sẽ phải nhảy bằng chân phải.

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 ký tự , tại mỗi bước giáo sư chọn một ký tự bất kỳ trong vũ điệu, nếu ký tự đó là sẽ được đổi thành và ngược lại, ký tự sẽ được đổi thành .

Yêu cầu: Cho 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.

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên dương ;
• dòng tiếp theo mỗi dòng chứa một vị trí mà giáo sư X đổi ký tự tại vị trí đó.

Dữ liệu ra:

• Ghi ra dòng, mỗi dòng ghi độ khó của điệu nhảy sau mỗi phép đổi ký tự.

Ví dụ:

Dữ liệu vào:

6 3
2
4
3

Dữ liệu ra:

4
2
3