• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

شاید باورش سخت باشد اما متن سوال به صورت صریح و عاری از داستان‌های تخیلی، در زیر آمده است:

برنامه‌ای بنویسید که با درنظرگرفتن دنباله‌ی اعداد صحیح$a_0,a_1,\cdots,a_{n-1}$ عدد طبیعی $l$ و عدد طبیعی $k$ تعداد زیردنباله‌های متوالی از $b_0,b_1,\cdots,b_{l-1}$ را که حداقل $k$ عدد متمایز دارند، محاسبه کند. دنباله‌ی $b_0,b_1,\cdots,b_{l-1}$ به صورت زیر ساخته می‌شود:

$$b_i = a_{(i , mod , n)} + \lfloor \frac{i}{n} \rfloor \times n , (0 \leq i \leq l-1)$$

ورودی

در سطر اول ورودی به ترتیب سه عدد طبیعی $k,l,n$ آمده است.

در سطر دوم ورودی $n$ عدد صحیح آمده است که اعداد دنباله‌‌ی $a_0,a_1,\cdots,a_{n-1}$ را نشان می‌دهند.

$$1 \leq n \leq 2\ 000$$ $$1 \leq k \leq l \leq 10^9$$ $$n \leq l$$

خروجی

در تنها سطر خروجی پاسخ مسئله را چاپ کنید.

زیر مسئله‌ها

زیرمسئله	نمره	محدودیت
۱	۱۲	$ k,l \le 1\ 000\ 000 $
۲	۲۱	$ k = 2 $
۳	۶۷	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

3 6 4
1 2 3

خروجی نمونه ۱

6

ورودی نمونه ۲

3 6 4
1 4 7

خروجی نمونه ۲

1

ورودی نمونه ۳

3 10 1
1 1 1

خروجی نمونه ۳

55