Дано положительное целое число \(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}]\).
Выходные данные
Выведите \(q\) строк. \(i\)-я из них должна содержать ответ на \(i\)-й запрос.
Примечание
В первом примере:
В первом запросе есть \(4\) массива, которые \(5\)-похожи на \([2,4]\): \([1,4],[3,4],[2,3],[2,5]\).
Во втором запросе есть \(3\) массива, которые \(5\)-похожи на \([4,5]\): \([1,5],[2,5],[3,5]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2 5
1 2 4 5
2 3
3 4
|
4
3
|
|
2
|
6 5 10
2 4 6 7 8 9
1 4
1 2
3 5
1 6
5 5
|
8
9
7
6
9
|