THỰC HÀNH

Trên hai đường thẳng song song L₁, L₂ người ta đánh dấu trên mỗi đường n điểm. Các điểm trên đường thẳng L₁ được đánh số 1, 2, …, n từ trái qua phải, còn các điểm trên đường thẳng L₂ được đánh số bởi d₁, d₂, …, d_n là một hoán vị của 1…n cũng được đánh dấu từ trái qua phải (hình dưới đây là một ví dụ cho n = 9)

1-----2-----3-----4-----5-----6-----7-----8-----9           L₁

2-----5-----3-----8-----7-----4-----6-----9-----1           L₂

Ta được phép nối điểm thứ i trên L₁ với điểm thứ j trên L₂ nếu |i – d_j| ≤ k.

Yêu cầu: Tìm cách nối được nhiều cặp điểm nhất với điều kiện các đoạn nối không được cắt nhau.

Input:

• Dòng đầu tiên chứa hai số nguyên n và k
• Dòng thứ hai chứa các số nguyên d₁, d₂, …, d_n.

Output:

Ghi ra số lượng cặp điểm nối lớn nhất tìm được.

Ví dụ:

Input:
3 1
3 2 1
Output:
2

Giới hạn:

• Subtask 1: n ≤ 1000, k = 0
• Subtask 2: n ≤ 1000, k ≤ 10⁹
• Subtask 3: n ≤ 10⁵, k = 3