F. Простая задача
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Для массива $$$b$$$ длины $$$m$$$ определим $$$f(b)$$$ следующим образом:

  • Массив $$$c$$$ длины $$$m$$$ называется красивым тогда и только тогда, когда для каждого $$$1 \le i \le m$$$ элемент $$$c_i$$$ равен либо $$$\max(b_1,b_2,\ldots,b_i)$$$, либо $$$\min(b_1,b_2,\ldots,b_i)$$$. Тогда $$$f(b)$$$ определяется как максимальное количество инверсий$$$^{\text{∗}}$$$ среди всех красивых массивов.

Вам дана перестановка$$$^{\text{†}}$$$ $$$p$$$ длины $$$n$$$. Требуется ответить на $$$q$$$ запросов, каждый из которых содержит два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$). Для каждого запроса вычислите $$$f([p_l,p_{l+1},\ldots,p_{r}])$$$.

$$$^{\text{∗}}$$$Количество инверсий массива $$$a$$$ длины $$$n$$$ определяется как количество пар целых чисел $$$(i,j)$$$, таких, что $$$1 \le i \lt j \le n$$$ и $$$a_i \gt a_j$$$.

$$$^{\text{†}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n,q \le 10^6$$$) — длину $$$p$$$ и количество запросов соответственно.

Вторая строка содержит $$$n$$$ различных целых чисел $$$p_1,p_2,\ldots,p_n$$$ ($$$1 \le p_i \le n$$$), задающих перестановку $$$p$$$.

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

Гарантируется, что сумма $$$n$$$ и сумма $$$q$$$ по всем наборам входных данных не превосходят $$$10^6$$$.

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

Для каждого набора входных данных выведите $$$q$$$ целых чисел, где $$$i$$$-е число обозначает ответ на $$$i$$$-й запрос.

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

В первом наборе входных данных:

  • Для второго запроса подмассив равен $$$[1,2]$$$. Можно взять $$$c=[\min(1),\min(1,2)]=[1,1]$$$, который имеет $$$0$$$ инверсий. Можно показать, что это максимальное количество инверсий среди всех красивых массивов.

В четвёртом наборе входных данных:

  • Для третьего запроса подмассив равен $$$[3,6,4,9]$$$. Можно взять $$$c=[\max(3),\max(3,6),\min(3,6,4),\min(3,6,4,9)]=[3,6,3,3]$$$, что даёт в сумме $$$2$$$ инверсии. Можно показать, что это максимальное количество инверсий среди всех красивых массивов.