Xóa đoạn nhiễu dài nhất

Bối cảnh

Một hệ thống ghi log sử dụng một giá trị đặc biệt x để đánh dấu các mẫu bị nhiễu. Nhiễu thường xuất hiện thành từng cụm liên tiếp. Do giới hạn dung lượng, bộ phận vận hành chỉ muốn loại bỏ một cụm nhiễu dài nhất khỏi dãy, còn mọi phần tử khác phải giữ nguyên thứ tự tương đối. Nếu có nhiều cụm x cùng độ dài lớn nhất, cụm xuất hiện sớm hơn phải được xóa. Nếu x không xuất hiện, dãy giữ nguyên.

Bài toán gồm hai pha khác nhau: trước hết phải nhận dạng đúng các đoạn liên tiếp bằng x và chọn đoạn cần xóa; sau đó thực hiện phép xóa ổn định trong mảng tĩnh bằng cách dịch phần đuôi sang trái. Đây là dạng bài gần với thao tác tiền xử lý dữ liệu thực tế hơn so với việc "xóa mọi x" và buộc người làm quản lý chính xác biên đoạn.

Không được dùng vector.erase. Mục tiêu là luyện tìm run trong mảng và thao tác xóa một đoạn bằng dịch phần tử.

Yêu cầu

1. Quét mảng theo từng run liên tiếp của x để tìm đoạn dài nhất, tie lấy đoạn đầu tiên.
2. Nếu không có x, in nguyên dãy.
3. Nếu có, dịch các phần tử sau đoạn xóa sang trái đúng bestLen ô và giảm n.

Input

Dòng 1: n x. Dòng 2: n số nguyên.

Output

Dòng 1: kích thước mới. Dòng 2: mảng sau khi xóa đoạn nhiễu dài nhất.

Ràng buộc

1 ≤ n ≤ 2000, |a[i]|,|x| ≤ 10^9.

Ví dụ 1

Input

10 0
1 0 0 2 0 0 0 3 0 4

Output

7
1 0 0 2 3 0 4

Giải thích

Giá trị nhiễu là x=0. Trong dãy có ba đoạn 0 liên tiếp: index 1..2 dài 2, index 4..6 dài 3 và index 8..8 dài 1. Đoạn dài nhất là 4..6, nên ba số 0 ở đó bị loại bỏ; phần đuôi 3 0 4 được dịch sang trái lấp chỗ trống. n giảm từ 10 xuống 7 và dãy còn lại là 1 0 0 2 3 0 4.

Ví dụ 2

Input

5 7
1 2 3 4 5

Output

5
1 2 3 4 5

Giải thích

Giá trị cần xóa là 7 nhưng dãy 1 2 3 4 5 không chứa phần tử nào bằng 7. Vì không tồn tại đoạn nhiễu, số phần tử vẫn là 5 và toàn bộ mảng được giữ nguyên. Output gồm n=5 và dãy ban đầu.

Thông tin học tập

• Module: M03
• Buổi: B10
• Loại bài: HOMEWORK
• Độ khó: Medium
• Concepts: static arrays, longest run, stable deletion, in-place shift, tie-break
• Giới hạn kiến thức: B01-B10
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100