ХХХ — удивительные существа, обладающие двумя манипуляторами (которые очень похожи на руки), на каждом из которых по $$$k$$$ сенсорных отростков, похожих на пальцы. Для общения они используют специальный передатчик, который посылает сигналы на разных частотных каналах. Нумерация отростков следующая:
Главное галактическое приветствие ХХХ — это строго определенная последовательность из $$$2k$$$ сигналов. Чтобы передать одно приветствие, они должны последовательно активировать каналы в следующем порядке:
Полная последовательность каналов для одного приветствия: $$$1, k+1, 2, k+2, \dots, k, 2k$$$.
Кто-то записал длинный фрагмент межзвездного эфира длины $$$n$$$, содержащий множество различных сигналов. Теперь он хочет проанализировать эти данные, чтобы понять, как часто ХХХ передавали свое приветствие. Он обратился к вам, как к самому опытному аналитику данных в вашей долине. У вас есть несколько запросов: для каждого временного промежутка от $$$l$$$ до $$$r$$$ вы хотите узнать, сколько существует подотрезков на заданном отрезке, таких, что они являются последовательностью приветствия.
Комбинация считается полностью переданной в промежутке $$$[l, r]$$$, если моменты времени всех $$$2k$$$ её сигналов принадлежат этому промежутку.
Первая строка содержит три целых числа $$$n$$$, $$$k$$$, $$$q$$$ $$$(1 \le n,\ k,\ q \le 2 \cdot 10^5)$$$ — длина записанной последовательности сигналов, количество сенсорных отростков на одном манипуляторе и количество ваших запросов.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2\cdot k$$$) — последовательность номеров каналов, записанная на фрагменте эфира.
Следующие $$$q$$$ строк содержат запросы. Каждая строка содержит два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$) — временной промежуток, для которого нужно найти количество полных приветствий.
Для каждого запроса выведите одно целое число в новой строке — количество раз, которое приветствие было полностью передано в промежутке с $$$l$$$-й по $$$r$$$-ю позицию включительно.
В задаче используется оценка по группам. Баллы за группу начисляются только при прохождении всех тестов группы. Группа тестируется только если все необходимые предыдущие группы были пройдены.
| Подзадача | Доп. ограничения | Баллы | Зависимые группы |
| $$$1$$$ | $$$n,k,q \le 100$$$ | $$$11$$$ | — |
| $$$2$$$ | $$$n,k,q \le 1000$$$ | $$$25$$$ | $$$1$$$ |
| $$$3$$$ | $$$k \le 100, n,q \le 2\cdot 10^{5}$$$ | $$$17$$$ | $$$1$$$ |
| $$$4$$$ | $$$k = 1$$$ | $$$9$$$ | — |
| $$$5$$$ | Для всех $$$i$$$ $$$ a_{i}=1$$$ | $$$7$$$ | — |
| $$$6$$$ | $$$ r-l \le 10 $$$ | $$$12$$$ | — |
| $$$7$$$ | Без дополнительных ограничений | $$$19$$$ | $$$1,2,3,4,5,6$$$ |
5 1 31 2 1 2 15 52 44 5
0 1 0
6 2 31 3 1 3 2 41 63 62 4
1 1 0
