write a go solution for G3. Yunli's Subarray Queries (extreme version)time limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputThis 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>=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^∗ 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+1sum_j=i+k-1^rf([a_i,a_i+1,ldots,a_j]).^∗If there exists a consecutive subarray of length k that starts at index i (1<=i<=|b|-k+1), then b_j=b_j-1+1 for all i<j<=i+k-1.InputThe first line contains t (1<=t<=10^4) — the number of test cases.The first line of each test case contains three integers n, k, and q (1<=k<=n<=2*10^5, 1<=q<=2*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<=a_i<=n).The following q lines contain two integers l and r (1<=l<=r<=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*10^5 and the sum of q over all test cases does not exceed 2*10^5.OutputOutput sum_i=l^r-k+1sum_j=i+k-1^rf([a_i,a_i+1,ldots,a_j]) for each query on a new line.ExampleInput57 2 41 2 3 2 1 2 34 61 72 73 78 4 24 3 1 1 2 4 3 23 61 55 4 24 5 1 2 31 41 510 4 82 3 6 5 8 9 8 10 10 12 76 101 91 63 94 102 101 810 7 43 4 5 3 4 5 9 10 8 91 92 101 102 9Output1
3
3
3
2
7
2
4
8
6
28
7
16
20
32
19
18
15
26
9
NoteIn the first query of the first testcase, we can calculate the answer for the query through the following:   i=4 and j=5: f([2,1])=1 because Yunli can set b_2=3, making a consecutive subarray of size 2 in 1 move.  i=4 and j=6: f([2,1,2])=0 because there is already a consecutive array of size 2.  i=5 and j=6: f([1,2])=0 because there is already a consecutive array of size 2. The answer to this query is 1+0+0=1.. Output only the code with no comments, explanation, or additional text.