P6465 [Chuanzhi Cup #2 Final] Course Scheduling

On Chuanzhi BoKe’s timetable, there are $n$ classes given in order. A class can be Java, Python, front-end development, etc. We use a positive number not greater than $n$ to represent the type of each class. Students can choose a short continuous segment of this class sequence as their study plan for one week. To make the study plan less boring, students do not want to take two consecutive classes of the same type. Specially, the first and the last class of the weekly plan also cannot be the same type. To ensure learning results, at least $l$ classes must be completed within the week. How many valid course-selection plans are there? Two plans are considered different as long as the chosen segment has at least one position different at the beginning or the end in the original sequence. Note that even if $l$ is 1, scheduling classes only once in a week is still invalid. At least 2 classes must be scheduled.

Each test consists of multiple test cases. The first line contains an integer $T$, which represents the number of test cases. For each test case, the first line contains two positive integers $n$ and $l$. The next line contains $n$ non-negative integers $c_i$ representing the course type IDs.

For each test case, output one integer per line, representing the number of plans.

**Sample Explanation** For the first test case, there are three ways: [1,2], [2,3], and [1,2,3]. For the second test case, since at least 3 classes must be chosen, there are only two ways: [1,2,3] and [2,3,1]. **Constraints** There are no more than 5 test cases. $1\le N \le 5 \times 10^5$, $1\le l,c_i \le N$. Translated by ChatGPT 5