Дана последовательность $A_1, A_2, \ldots, A_N$ длины $N$. Напишите программу, обрабатывающую следующие запросы:

• s e: Выведите количество пар $(i, j)$ таких, что $s \le i < j \le e$ и $A_i > A_j$. ($1 \le s \le e \le N$)

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

Первая строка содержит длину последовательности $N$ ($1 \le N \le 100{,}000$) и количество запросов $M$ ($1 \le M \le 100{,}000$).

Вторая строка содержит $A_1, A_2, \ldots, A_N$. ($1 \le A_i \le 1{,}000{,}000{,}000$)

Следующие $M$ строк содержат по одному запросу в каждой.

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

Для каждого запроса выведите его ответ на отдельной строке.

Примеры

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

5 3
1 4 2 3 1
1 2
3 5
1 5

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

0
2
5