codeforces#P2009G1. Yunli's Subarray Queries (easy version)
Yunli's Subarray Queries (easy version)
Description
This is the easy version of the problem. In this version, it is guaranteed that $r=l+k-1$ for all queries.
For an arbitrary array $b$, Yunli can perform the following operation any number of times:
- Select an index $i$. Set $b_i = x$ where $x$ is any integer she desires ($x$ is not limited to the interval $[1,n]$).
Denote $f(b)$ as the minimum number of operations she needs to perform until there exists a consecutive subarray$^{\text{∗}}$ of length at least $k$ in $b$.
Yunli is given an array $a$ of size $n$ and asks you $q$ queries. In each query, you must output $\sum_{j=l+k-1}^{r} f([a_l, a_{l+1}, \ldots, a_j])$. Note that in this version, you are only required to output $f([a_l, a_{l+1}, \ldots, a_{l+k-1}])$.
$^{\text{∗}}$If there exists a consecutive subarray of length $k$ that starts at index $i$ ($1 \leq i \leq |b|-k+1$), then $b_j = b_{j-1} + 1$ for all $i < j \leq i+k-1$.
The first line contains $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
The first line of each test case contains three integers $n$, $k$, and $q$ ($1 \leq k \leq n \leq 2 \cdot 10^5$, $1 \leq q \leq 2 \cdot 10^5$) — the length of the array, the length of the consecutive subarray, and the number of queries.
The following line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq n$).
The following $q$ lines contain two integers $l$ and $r$ ($1 \leq l \leq r \leq n$, $r=l+k-1$) — the bounds of the query.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ and the sum of $q$ over all test cases does not exceed $2 \cdot 10^5$.
Output $\sum_{j=l+k-1}^{r} f([a_l, a_{l+1}, \ldots, a_j])$ for each query on a new line.
Input
The first line contains $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
The first line of each test case contains three integers $n$, $k$, and $q$ ($1 \leq k \leq n \leq 2 \cdot 10^5$, $1 \leq q \leq 2 \cdot 10^5$) — the length of the array, the length of the consecutive subarray, and the number of queries.
The following line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq n$).
The following $q$ lines contain two integers $l$ and $r$ ($1 \leq l \leq r \leq n$, $r=l+k-1$) — the bounds of the query.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ and the sum of $q$ over all test cases does not exceed $2 \cdot 10^5$.
Output
Output $\sum_{j=l+k-1}^{r} f([a_l, a_{l+1}, \ldots, a_j])$ for each query on a new line.
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
Note
In the first query of the first testcase, $b=[1,2,3,2,1]$. Yunli can make a consecutive subarray of length $5$ in $2$ moves:
- Set $b_4=4$
- Set $b_5=5$
In the second query of the first testcase, $b=[2,3,2,1,2]$. Yunli can make a consecutive subarray of length $5$ in $3$ moves:
- Set $b_3=0$
- Set $b_2=-1$
- Set $b_1=-2$