LCSUB - Dãy con có giá trị liên tiếp dài nhất
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: middlest

"Cho dãy A gồm k phần tử, mỗi phần tử có giá trị trong đoạn [1; n] và khác nhau đôi một. Hãy tìm một dãy con dài nhất mà giá trị của các phần tử trong dãy con đó là liên tiếp nhau."

Bài toán trên đã không còn gì xa lạ đối với các học sinh chuyên Tin. Vì vậy, thầy giáo đã mở rộng thành một bài toán mới được phát biểu như sau:

Cho dãy A gồm k phần tử, mỗi phần tử có giá trị trong đoạn [1; n] và khác nhau đôi một. Tuy nhiên có thể có một phần tử có giá trị bằng 0, đây là một phần tử đặc biệt, bạn có thể gán bất cứ giá trị nào trong đoạn [1; n] sao cho phần tử này sao cho giá trị đó khác với giá trị của các phần tử còn lại trong dãy (việc gán này là bắt buộc). Sau đó hãy tìm một dãy con dài nhất mà giá trị của các phần tử trong dãy là liên tiếp nhau.

Input

Dòng đầu ghi hai số nguyên n, k (1 <= n <= 105, 1 <= k <= n)

k dòng tiếp theo, mỗi dòng ghi giá trị của phần tử thứ k

Output

In ra độ dài của dãy con dài nhất mà giá trị của các phần tử trong dãy là liên tiếp nhau.

Ví dụ

  • input
    7 5
    6
    2
    0
    4
    7
    output
    4

Ta có thể gán giá trị 5 cho phần tử giá trị 0, khi đó dãy trở thành 6, 2, 5, 4, 7. Dễ thấy dãy con 6, 5, 4, 7 có các phần tử có giá trị liên tiếp nhau là 4, 5, 6, 7 và có độ dài 4

Back to Top