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

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

در ورودی نمونه‌ی اول، دنباله‌ی $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$ است.

• سوال بعد