G2. Запросы подмассивов Юнли (сложная версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. В этой версии гарантируется, что $$$r \geq l+k-1$$$ для всех запросов.

Для произвольного массива $$$b$$$ Юнли может выполнять следующую операцию любое количество раз:

  • Выбрать индекс $$$i$$$. Присвоить $$$b_i = x$$$, где $$$x$$$ — любое целое число, которое она хочет ($$$x$$$ не ограничено интервалом $$$[1,n]$$$).

Обозначим $$$f(b)$$$ как минимальное количество операций, которые ей нужно выполнить, чтобы в массиве $$$b$$$ существовал последовательный подмассив$$$^{\text{∗}}$$$ длиной не менее $$$k$$$.

Юнли дан массив $$$a$$$ размером $$$n$$$, и она задает вам $$$q$$$ запросов. В каждом запросе вы должны вывести $$$\sum_{j=l+k-1}^{r} f([a_l, a_{l+1}, \ldots, a_j])$$$.

$$$^{\text{∗}}$$$Если существует последовательный подмассив длиной $$$k$$$, который начинается с индекса $$$i$$$ ($$$1 \leq i \leq |b|-k+1$$$), то $$$b_j = b_{j-1} + 1$$$ для всех $$$i < j \leq i+k-1$$$.

Входные данные

Первая строка содержит $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$k$$$ и $$$q$$$ ($$$1 \leq k \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq q \leq 2 \cdot 10^5$$$) — длину массива, длину последовательного подмассива и количество запросов.

Следующая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, ..., a_n$$$ ($$$1 \leq a_i \leq n$$$).

Следующие $$$q$$$ строк содержат по два целых числа $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq n$$$, $$$r \geq l+k-1$$$) — границы запроса.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$, а сумма $$$q$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Выведите $$$\sum_{j=l+k-1}^{r} f([a_l, a_{l+1}, \ldots, a_j])$$$ для каждого запроса на новой строке.

Пример
Входные данные
3
7 5 3
1 2 3 2 1 2 3
1 7
2 7
3 7
8 4 2
4 3 1 1 2 4 3 2
3 6
1 5
5 4 2
4 5 1 2 3
1 4
1 5
Выходные данные
6
5
2
2
5
2
3
Примечание

Во втором запросе первого набора входных данных мы вычисляем следующие значения функции:

  • $$$f([2,3,2,1,2])=3$$$, потому что Юнли может присвоить $$$b_3=4$$$, $$$b_4=5$$$ и $$$b_5=6$$$, сделав последовательный подмассив размером $$$5$$$ за $$$3$$$ хода.
  • $$$f([2,3,2,1,2,3])=2$$$, потому что мы можем присвоить $$$b_3=0$$$ и $$$b_2=-1$$$, сделав последовательный подмассив размером $$$5$$$ за $$$2$$$ хода (начиная с позиции $$$2$$$).

Ответ на этот запрос равен $$$3+2=5$$$.