This is the extreme version of the problem. In this version, the output of each query is different from the easy and hard versions. It is also 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_{i=l}^{r-k+1} \sum_{j=i+k-1}^{r} f(a_i, a_{i+1}, \ldots, a_j)). (^{\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, ..., 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 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_{i=l}^{r-k+1} \sum_{j=i+k-1}^{r} f(a_i, a_{i+1}, \ldots, a_j)) for each query on a new line. In the first query of the first testcase, we can calculate the answer for the query through the following: (i = 4) and (j = 5)