Cho một dãy số nguyên \(A_1, A_2, \dots, A_n\). Một đoạn con liên tiếp của \(A\) từ \(L\) đến \(R\), gọi là đoạn \([L, R]\) và gồm các phần tử \(A_L, A_{L+1}, \dots, A_R\), được gọi là hoàn hảo nếu:

• Tất cả các phần tử trong đoạn đôi một phân biệt, hay nói cách khác \(A_i \neq A_j\) với mọi \(L \le i < j \le R\).
• Chênh lệch giữa hai phần tử bất kỳ trong đoạn không vượt quá \(k\), hay nói cách khác, \(|A_i - A_j| \le k\) với mọi \(L \le i < j \le R\).

Bạn hãy tìm \(m\) đoạn con liên tiếp không giao nhau của \(A\) sao cho tất cả các đoạn con đều hoàn hảo và tổng độ dài của chúng là lớn nhất.

Hai đoạn con \((L_1, R_1)\) và \((L_2, R_2)\) được tính là giao nhau nếu chúng có chung ít nhất một phần tử. Độ dài của đoạn con \((L, R)\) là \(R - L + 1\).

Input

• Dòng đầu tiên gồm ba số nguyên dương \(n, k, m\) (\(1 \le n \le 5 \times 10^5\), \(1 \le k \le 10^9\), \(1 \le m \le 20\)).
• Dòng tiếp theo gồm \(n\) số nguyên dương \(A_1, A_2, \dots, A_n\) (\(1 \le A_i \le 10^9\)).

Output

• Một dòng duy nhất gồm tổng độ dài lớn nhất tìm được.

Example

8 3 2
1 5 2 3 5 1 2 4

6

Scoring

• \(6\%\) số điểm có \(m = 1\) và \(n \le 80\).
• \(8\%\) số điểm khác có \(m = 1\) và \(n \le 200\).
• \(8\%\) số điểm khác có \(m = 1\) và \(n \le 2000\).
• \(9\%\) số điểm khác có \(m = 1\) và \(k = 10^9\).
• \(9\%\) số điểm khác có \(m = 1\).
• \(10\%\) số điểm khác có \(m = 2\) và \(n \le 2000\).
• \(11\%\) số điểm khác có \(m = 2\).
• \(11\%\) số điểm khác có \(m = 3\) và \(n \le 2000\).
• \(14\%\) số điểm khác có \(n \le 2000\).
• \(14\%\) số điểm còn lại không có giới hạn gì thêm.