BODEN - Dãy bóng đèn
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 2.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: trungvt130584

      Nam rất thích chơi với ánh sáng, cậu có một dãy gồm N bóng đèn xếp theo thứ tự từ 1 đến N. Mỗi bóng đèn có một công tắc mà khi chạm vào nó, bóng đèn đang tắt sẽ chuyển sang trạng thái sáng và ngược lại, bóng đèn đang sáng thì trở thành tắt. Đầu tiên các bóng đèn đang tắt. Trò chơi của Nam bao gồm Q lần chạm vào công tắc, mỗi lần chỉ chạm một công tắc. Sau mỗi lần chạm, Nam muốn tìm một dãy con các bóng đèn mà trong dãy con đó, các bóng đèn có trạng thái tắt/mở xen kẽ lẫn nhau. Bạn hãy giúp Nam tìm dãy xen kẽ dài nhất sau mỗi lần chạm nhé.

Dãy dài nhất 5 bóng đèn tắt/mở xen kẽ

Dữ liệu nhập:

- Dòng đầu tiên chứa hai số nguyên N và Q (1 ≤ N, Q ≤ 200.000).

- Trong Q dòng tiếp theo, dòng thứ i chứa một số nguyên dương là vị trí của bóng đèn mà Nam tắt/mở trong lần chạm thứ i.

Dữ liệu xuất:

- Gồm Q dòng, mỗi dòng chứa 1 số nguyên là kết quả của lần chạm thứ i. Số nguyên này xác định chiều dài của dãy con các bóng đèn mà có trạng thái tắt/mở xen kẽ lẫn nhau.

(trước khi bắt đầu trò chơi thì các bóng đèn đều ở trạng thái tắt)

Ví dụ

  • input
    6 2
    2
    4
    output
    3
    5
  • input
    6 5
    4
    1
    1
    2
    6
    output
    3
    3
    3
    5
    6
Back to Top