Cắt dải giấy

Cho một dải giấy gồm $n$ số nguyên $a_1,a_2,\dots ,a_n$ viết từ trái sang phải.

Bạn cần cắt dải giấy thành một số đoạn liên tiếp (có thể chỉ một đoạn). Mỗi đoạn phải thỏa mãn đồng thời hai điều kiện:

• Đoạn chứa ít nhất $l$ số.
• Hiệu giữa số lớn nhất và số nhỏ nhất trong đoạn không vượt quá $s$.

Hãy tìm số đoạn ít nhất có thể cắt được sao cho mọi đoạn đều thỏa mãn các điều kiện trên. Nếu không tồn tại cách cắt hợp lệ, in ra $-1$.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $s$, $l$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

• In ra một số nguyên là số đoạn ít nhất, hoặc $-1$ nếu không có cách cắt hợp lệ.

Ràng buộc

• $1\le n\le {10}^5$
• $0\le s\le {10}^9$
• $1\le l\le {10}^5$
• $-{10}^9\le a_i\le {10}^9$

Ví dụ