B. Замена и возрастание
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано положительное целое число $$$k$$$. Два массива называются $$$k$$$-похожими, если:

  • они строго возрастающие;
  • они имеют одинаковую длину;
  • все их элементы — это положительные целые числа между $$$1$$$ и $$$k$$$ (включительно);
  • они различаются в ровно одной позиции.

Вам дано число $$$k$$$, строго возрастающий массив $$$a$$$ и $$$q$$$ запросов. Для каждого запроса вам даны два целых числа $$$l_i \leq r_i$$$. Ваша задача найти, сколько массивов $$$b$$$ существует таких, что $$$b$$$ $$$k$$$-похож на массив $$$[a_{l_i},a_{l_i+1}\ldots,a_{r_i}]$$$.

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

В первой строке находятся три целых числа $$$n$$$, $$$q$$$ и $$$k$$$ ($$$1\leq n, q \leq 10^5$$$, $$$n\leq k \leq 10^9$$$) — длина массива $$$a$$$, количество запросов и число $$$k$$$.

Во второй строке находятся $$$n$$$ целых чисел $$$a_1, a_2, \ldots,a_n$$$ ($$$1 \leq a_i \leq k$$$). Этот массив строго возрастающий: $$$a_1 < a_2 < \ldots < a_n$$$.

Каждая из следующих $$$q$$$ строк содержит два целых числа $$$l_i$$$, $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$).

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

Выведите $$$q$$$ строк. $$$i$$$-я из них должна содержать ответ на $$$i$$$-й запрос.

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

В первом примере:

В первом запросе есть $$$4$$$ массива, которые $$$5$$$-похожи на $$$[2,4]$$$: $$$[1,4],[3,4],[2,3],[2,5]$$$.

Во втором запросе есть $$$3$$$ массива, которые $$$5$$$-похожи на $$$[4,5]$$$: $$$[1,5],[2,5],[3,5]$$$.