This is the hard version of the problem. In this version, it is guaranteed that $r \geq 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])$.

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, ..., 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 \geq l+k-1$) — the bounds of the query.

It is guaranteed 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.

见题面 Input 部分

见题面 Output 部分

In the second query of the first testcase, we calculate the following function values:

• $f([2,3,2,1,2])=3$ because Yunli can set $b_3=4$, $b_4=5$, and $b_5=6$, making a consecutive subarray of size $5$ in $3$ moves.
• $f([2,3,2,1,2,3])=2$ because we can set $b_3=0$ and $b_2=-1$, making a consecutive subarray of size $5$ in $2$ moves (starting at position $2$)

The answer to this query is $3+2=5$.