Khảo cổ

Trong một cuộc khai quật tại thành cổ Ibibiqinhi, nhà khảo cổ 3M phát hiện một cuộn giấy cổ
kỳ lạ, được cho là chứa đựng những bí ẩn về nền văn minh đã mất. Cuộn giấy này khắc một
chuỗi gồm \(n\) ký hiệu cổ, mỗi ký hiệu là một số nguyên tượng trưng cho những bí mật chưa
được giải mã. Truyền thuyết kể rằng, chỉ khi 3M giải mã được tất cả mảnh bí ẩn ẩn trong
chuỗi ký hiệu, những bí mật cổ xưa mới được hé lộ. Một mảnh bí ẩn được định nghĩa là một
đoạn liên tiếp trên cuộn giấy thỏa mãn hai điều kiện:

• Trong đoạn đó có đúng \(k\) ký hiệu khác nhau.
• Độ dài của đoạn nằm trong khoảng từ \(l\) đến \(r\) (bao gồm cả hai đầu).

Nhiệm vụ của bạn là giúp nhà khảo cổ 3M xác định có bao nhiêu đoạn như vậy.

Input

Nhập vào file văn bản ARCHEO.INP:

• Dòng đầu tiên chứa hai số nguyên dương \(n, k, l, r\) \((1 \leq l \leq r \leq n \leq 10^5, 1 \leq k \leq n)\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2,..., a_n (1 \leq |a_i| \leq 10^9)\).

Output

Ghi ra file văn bản ARCHEO.OUT:

• Là số đoạn con thỏa mãn đề bài.

Example

5 2 2 3
1 2 1 3 2

5

6 3 1 6
1 2 3 1 2

7

Scoring

• \(30\%\) số test tương ứng với \(30\%\) số điểm của \(n \leq 100\).
• \(20\%\) số test tương ứng với \(20\%\) số điểm của \(n \leq 10^3\).
• \(30\%\) số test tương ứng với \(30\%\) số điểm có \(l = 1, r = n\).
• \(20\%\) số test còn lại tương ứng với \(20\%\) số điểm của bài không có ràng buộc gì thêm.