这是问题的简单版本。在此版本中,保证所有查询$$$r=l+k-1$$$。
对于任意数组$$$b$$$,Yunli可以执行任意多次以下操作:
- 选择索引 $$$i$$$。设置$$$b_i = x$$$,其中$$$x$$$ 是她想要的任何整数($$$x$$$ 不限于区间$$$[1,n]$$$)。
将$$$f(b)$$$表示为她需要执行的最少操作数,直到$$$b$$$中存在长度至少$$$k$$$的连续子数组$$$^{\text{*}}$$$。
Yunli 被给予一个大小为 $$$n$$$ 的数组 $$$a$$$ 并要求你 $$$q$$$ 查询。在每个查询中,您必须输出 $$$\sum_{j=l+k-1}^{r} f([a_l, a_{l+1}, \ldots, a_j])$$$。请注意,在此版本中,您只需输出 $$$f([a_l, a_{l+1}, \ldots, a_{l+k-1}])$$$。
输入
第一行包含 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含三个整数 $$$n$$$、$$$k$$$ 和 $$$q$$$ ($$$1 \leq k \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq q \leq 2 \cdot 10^5$$$) — 数组的长度、连续子数组的长度,以及查询的数量。
以下行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$)。
以下 $$$q$$$ 行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l \leq r \leq n$$$, $$$r=l+k-1$$$) — 查询的边界。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$,所有测试用例的 $$$q$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
为新行上的每个查询输出 $$$\sum_{j=l+k-1}^{r} f([a_l, a_{l+1}, \ldots, a_j])$$$。
示例
输入 #1
3 7 5 3 1 2 3 2 1 2 3 1 5 2 6 3 7 8 4 2 4 3 1 1 2 4 3 2 3 6 2 5 5 4 2 4 5 1 2 3 1 4 2 5
输出 #1
2 3 2 2 2 2 1
注意
在第一个测试用例的第一个查询中,$$$b=[1,2,3,2,1]$$$。云里可以在$$$2$$$移动中生成长度为$$$5$$$的连续子数组:
- 设置$$$b_4=4$$$
- 设置$$$b_5=5$$$
在第一个测试用例的第二个查询中,$$$b=[2,3,2,1,2]$$$。云里可以在 $$$3$$$ 移动中生成长度为 $$$5$$$ 的连续子数组:
- 设置$$$b_3=0$$$
- 设置$$$b_2=-1$$$
- 设置$$$b_1=-2$$$