Dany jest ciąg $A_1, A_2, \ldots, A_N$ o długości $N$. Napisz program, który przetwarza następujące zapytania:

• s e: Wypisz liczbę par $(i, j)$ takich, że $s \le i < j \le e$ oraz $A_i > A_j$. ($1 \le s \le e \le N$)

Wejście

Pierwszy wiersz zawiera długość ciągu $N$ ($1 \le N \le 100\,000$) oraz liczbę zapytań $M$ ($1 \le M \le 100\,000$).

Drugi wiersz zawiera $A_1, A_2, \ldots, A_N$. ($1 \le A_i \le 1\,000\,000\,000$)

Kolejne $M$ wierszy zawiera po jednym zapytaniu.

Wyjście

Dla każdego zapytania wypisz odpowiedź w osobnym wierszu.

Przykład

Przykładowe wejście 1

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

Przykładowe wyjście 1

0
2
5