课程安排(Course Scheduling)

题目描述

传智播客的课表上按顺序提供 $n$ 节课程，课程可能是 Java、Python 或者前端开发等等，我们用不超过 $n$ 的正数代表每一节课程的种类。学员可以从这个课程序列选取连续的一小段的课程序列，作为一周的学习任务。

为了使学习任务不那么枯燥，学员不想连续上两节相同的课。特殊的，这一周学习任务的开头和结尾也不能是相同的课。为了保证学习效果，一周内至少要学完 $l$ 节课程。

请问，我们有多少种合法的选课方案？

两种选课方案，只要选取的课程序列在原序列的开头和结尾有至少一个位置不一致，那么就可以认为是不同的选课方案。注意，即使 $l$ 是 1，一周只安排一次课也是不合法的，至少需要安排 2 次课。

输入格式

每个测试点由多组数据组成。

第一行为一个整数 $T$，代表数据的组数。

对于每组数据，第一行输入两个正整数 $n$ 和 $l$。接下来一行输入 $n$ 个非负整数 $c_i$ 表示课程种类编号。

输出格式

对于每组数据，输出一行一个数，表示方案数。

样例输入 #1

2
3 1
1 2 3
5 3
1 2 3 1 1

样例输出 #1

3
2

数据范围

样例解释

对于第一组数据，有 [1,2] 和 [2,3] 和 [1,2,3] 三种方法。

对于第二组数据，由于至少要选 3 门课，只有 [1,2,3] 和 [2,3,1] 两种方法。

数据范围

测试数据不超过 5 组，$1\le N \le 5 \times 10^5$，$1\le l,c_i \le N$

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1650。

测试点分布

出处：原题链接