G3. Запросы подмассивов Юнли (экстремальная версия)
ограничение по времени на тест
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_{i=l}^{r-k+1} \sum_{j=i+k-1}^{r} f([a_i, a_{i+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_{i=l}^{r-k+1} \sum_{j=i+k-1}^{r} f([a_i, a_{i+1}, \ldots, a_j])$$$ для каждого запроса на новой строке.

Пример
Входные данные
5
7 2 4
1 2 3 2 1 2 3
4 6
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
10 4 8
2 3 6 5 8 9 8 10 10 1
2 7
6 10
1 9
1 6
3 9
4 10
2 10
1 8
10 7 4
3 4 5 3 4 5 9 10 8 9
1 9
2 10
1 10
2 9
Выходные данные
1
3
3
3
2
7
2
4
8
6
28
7
16
20
32
19
18
15
26
9
Примечание

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

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

Ответ на этот запрос равен $$$1+0+0=1$$$.