CF2009G1 Yunli's Subarray Queries (easy version)

**这是该问题的简单版本。保证所有问题中，$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

第一行包含 $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])$。

保证在所有样例中，$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](https://www.luogu.com.cn/user/946085)。