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

---

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

برنامه‌ای بنویسید که با درنظرگرفتن دنباله‌ی اعداد صحیح\(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