Bất kì học sinh nào tham gia kì thi VOI đều biết về bài toán dãy con tăng dài nhất. Dãy con tăng dài nhất của dãy 𝑎1 , 𝑎2 , … , 𝑎𝑛 là dãy 1 ≤ 𝑝1 < 𝑝2 < ⋯ < 𝑝𝑘 ≤ 𝑛 (trong đó 𝑘 là số nguyên lớn nhất) sao cho 𝑎𝑝1 < 𝑎𝑝2 < ⋯ < 𝑎𝑝𝑘 .
Anh là một học sinh thông minh, thích tìm tòi, khám phá nhiều điều mới lạ nên bạn đã thay đổi một chút nội dung của bài toán này. Trước tiên, Anh chọn một đoạn con liên tiếp trong dãy 𝑎1 , 𝑎2 , … , 𝑎𝑛 và một số nguyên 𝑑 (−𝑥 ≤ 𝑑 ≤ 𝑥). Anh thực hiện tăng giá trị các phần tử trong đoạn con đó lên 𝑑 (𝑑 có thể bằng 0). Sau phép biến đổi, độ dài của dãy con tăng dài nhất sẽ dài hơn và Anh muốn biết độ dài này là bao nhiêu. Các bạn hãy viết chương trình giúp Anh nhé!
Dữ liệu:
- Dòng đầu gồm hai số nguyên 𝑛 và 𝑥 (1 ≤ 𝑛 ≤ 200 000, 0 ≤ 𝑥 ≤ 109 ) lần lượt là độ dài của dãy ban đầu và giới hạn cho giá trị 𝑑;
- Dòng thứ hai gồm 𝑛 số nguyên 𝑎1 , 𝑎2 , … , 𝑎𝑛(1 ≤ 𝑎𝑖 ≤ 109 , 𝑖 = 1. . 𝑛). Các số trên một dòng của input file được ghi cách nhau bởi dấu cách.
Kết quả:
Ghi ra một số nguyên duy nhất là độ dài của dãy con tăng dài nhất sau phép biến đổi.
Input
8 10
7 3 5 12 2 7 3 4
Output
5
Ràng buộc:
- 30% số điểm tương ứng với 30% số test có 𝑛 ≤ 1 000;
- 30% số điểm tương ứng với 30% số test có 𝑥 = 0;
- 40% số điểm tương ứng với 40% số test không có ràng buộc gì thêm.
Nguồn: PREVNOI TEAM 20182019 Hải Phòng