====== Abstract ======

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

برنامه‌ای بنویسید که با در نظر گرفتن دنباله‌ی اعداد صحیح $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\ \mathrm{mod}\ n)} + \lfloor \frac{i}{n}\rfloor \times n\ \ \ (0\leq i\leq l-1)$$


===== ورودی =====

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

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


===== خروجی =====

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


===== زیرمسئله‌ها =====


  * زیرمسئله اول (۱۲ نمره): $k,l\leq 10^{6}$
  * زیرمسئله دوم (۲۱ نمره): $k=2$
  * زیرمسئله سوم (۶۷ نمره): بدون محدودیت اضافی


===== محدودیت‌ها =====

  * $1\leq n\leq 2000$
  * $1\leq k\leq l\leq 10^{9}$
  * $n\leq l$

===== ورودی و خروجی نمونه =====

<WRAP :en>
^  ورودی نمونه  ^  خروجی نمونه  ^
|3 6 4 \\ 1 2 3|6|
|3 6 4 \\ 1 4 7|1|
|3 10 1 \\ 1 1 1|55|
</WRAP>
===== شرح ورودی و خروجی نمونه =====

در ورودی نمونه‌ی اول، دنباله‌ی $b_i$ها برابر است با:
$1\ 2\ 3\ 4\ 5\ 6$
. با توجه به این‌که تمامی اعداد این دنباله‌ متمایز هستند، بنابراین هر زیر‌دنباله‌ای که طول حداقل $k=4$ داشته باشد، باید در پاسخ در نظر گرفته شود. پس پاسخ مسئله برابر است با تعداد زیر‌دنباله‌های متوالی از $b_i$‌ها که حداقل چهار عضو دارند. این تعداد برابر است با:
$3 + 2 + 1 = 6$

در ورودی نمونه‌ی دوم، دنباله‌ی $b_i$‌ها برابر است با:
$1\ 4\ 7\ 4\ 7\ 10$.
با توجه به این‌که تنها زیر‌دنباله‌ای که حداقل چهار عضو متمایز دارد، برابر با کل دنباله‌ی $b_0,b_1,\cdots,b_5$ است بنابراین پاسخ مسئله برابر با $1$ است.

  * [[سوال ۲|سوال بعد]]