Chia Nhóm Theo Độ Chênh · canuc80k2618

Có $n$ thẻ, thẻ thứ $i$ mang giá trị $a_{i}$ . Hãy chia toàn bộ các thẻ vào một số nhóm không rỗng. Mỗi nhóm phải có ít nhất $k$ thẻ và hiệu giữa giá trị lớn nhất với nhỏ nhất trong nhóm không vượt quá $d$ .

Input

Dòng đầu chứa $n, k, d$ . Dòng thứ hai chứa $n$ số nguyên $a_{i}$ .

Output

In YES nếu tồn tại cách chia hợp lệ; ngược lại in NO.

Constraints

$1 \leq k \leq n \leq 5 \cdot 1 0^{5}$ .
$0 \leq d \leq 1 0^{9}$ .
$1 \leq a_{i} \leq 1 0^{9}$ .

Scoring

Subtask $1$ ( $50%$ ): $n \leq 12$ .
Subtask $2$ ( $50%$ ): Không có giới hạn bổ sung.

Example

Test 1

Input

7 3 2
12 1 11 3 10 2 12

Output

YES

Giải thích: Hai nhóm ${1, 2, 3}$ và ${10, 11, 12, 12}$ có kích thước $3, 4$ và cùng độ chênh $2$ .

Ý tưởng: Sắp các giá trị tăng dần. Có thể chọn một phân hoạch tối ưu thành các đoạn liên tiếp trong thứ tự này. Đặt dp[i] đúng khi i phần tử đầu chia được hợp lệ. Với nhóm cuối kết thúc tại i, điểm cắt j phải thỏa dp[j], i-j≥k và a_i-a_(j+1)≤d.
Ý tưởng: Dùng hai con trỏ tìm đầu trái nhỏ nhất còn nằm trong khoảng giá trị d; các điểm cắt hợp lệ tạo một đoạn. Mảng cộng dồn của dp trả lời trong O(1) liệu đoạn đó có trạng thái đúng.
Chứng minh: Mọi phân hoạch có một nhóm cuối thỏa các điều kiện trên. Ngược lại, nối một đoạn hợp lệ vào tiền tố reachable tạo phân hoạch hợp lệ. Quy nạp theo i chứng minh dp[n] đúng khi và chỉ khi có lời giải.
Độ phức tạp: O(n log n) thời gian và O(n) bộ nhớ.