题目描述

这是该问题的简单版本。保证所有问题中，$r=l+k-1$ 。

题面描述

对于任意数组 $b$，可以多次执行以下操作：

• 选择一个下标 $i$，令 $b_i=x$， 其中 $x$ 为任意整数（不限于区间 $[1,n]$ ）。

记 $f(b)$ 为数组 $b$ 中，存在一个长度至少为 $k$ 的连续子数组$^*$ 的最小操作次数。

给出一个大小为 $n$ 的数组 $a$，然后询问 $q$ 个问题。在每个问题中，你必须输出 $∑_{j=l+k-1}^r f([a_l,a_{l+1},…,a_j])$。注意在该题中，只被要求输出$f([a_l,a_{l+1},…,a_j])$。

$^*$ 如果存在一个长度为 $k$ 的连续子数组，且开始于下标 $i$ $(1≤i≤|b|−k+1)$，则对于所有$i<j≤i+k−1$，满足 $b_j=b_{j−1}+1$。

输入格式

第一行包含 $t$ $(1≤t≤10^4 )$ ——样例的组数。

每组样例的第一行包含三个整数 $n,k$，和 $q$ $(1≤k≤n≤2⋅10^5 , 1≤q≤2⋅10^5 )$ ——数组的长度、连续子数组的长度和问题的个数。

接下去一行包含 $n$ 个整数 $a_1,a_2,…,a_n$ $(1≤a_i≤n )$。

接下去 $q$ 行包含两个整数 $l$ 和 $r$ $(1≤l≤r≤n , r=l+k−1)$。

输出格式

对于每个问题，输出仅一行—— $∑_{j=l+k-1}^r f([a_l,a_{l+1},…,a_j])$。

样例

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

2
3
2
2
2
2
1

样例说明

保证在所有样例中，$n$ 的总和不超过 $2⋅10^5$，$q$ 的总和不超过$2⋅10^5$。

在第一个样例的第一个问题中，$b=[1,2,3,2,1]$。可以执行两次操作以构造一个长度为 $5$ 的连续子数组：

• 令$b_4=4$；
• 令$b_5=5$。

经过以上操作后，$b=[1,2,3,4,5]$。

在第一个样例的第二个问题中，$b=[2,3,2,1,2]$。可以执行三次操作以构造一个长度为 $5$ 的连续子数组：

• 令$b_3=0$；
• 令$b_2=-1$；
• 令$b_1=-2$。

经过以上操作后，$b=[-2,-1,0,1,2]$。

翻译提供：zhoujy1209。

来源

Codeforces 2009G1，英文题名 Yunli's Subarray Queries (easy version)。