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

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

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

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

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

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

$$$^{\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, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$).

Следующие $$$q$$$ строк содержат по два целых числа $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq n$$$, $$$r=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 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
Примечание

В первом запросе первого примера, $$$b=[1,2,3,2,1]$$$. Юнли может сделать последовательный подмассив длиной $$$5$$$ за $$$2$$$ хода:

  • Присвоить $$$b_4=4$$$
  • Присвоить $$$b_5=5$$$
В итоге $$$b=[1, 2, 3, 4, 5]$$$.

Во втором запросе первого примера, $$$b=[2,3,2,1,2]$$$. Юнли может сделать последовательный подмассив длиной $$$5$$$ за $$$3$$$ хода:

  • Присвоить $$$b_3=0$$$
  • Присвоить $$$b_2=-1$$$
  • Присвоить $$$b_1=-2$$$
В итоге $$$b=[-2, -1, 0, 1, 2]$$$.