+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- شاید باورش سخت باشد اما متن سوال به صورت صریح و عاری از داستان‌های تخیلی، در زیر آمده است: برنامه‌ای بنویسید که با درنظرگرفتن دنباله‌ی اعداد صحیح$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 ```