시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 1024 MB103644159.420%

문제

Neka je zadana permutacija $P$ duljine $N$. Permutacija duljine $N$ je niz čiji su elementi različiti prirodni brojevi od $1$ do $N$. Broj inverzija neke permutacije je broj parova $(i, j)$ takvih da je $1 ≤ i < j ≤ N$ i $P_i > P_j$.

Isto tako, broj inverzija permutacija $P$ na intervalu od a do b je broj parova $(i, j)$ takvih da je $a ≤ i < j ≤ b$ i $P_i > P_j$.

Tvoj zadatak je da za zadanu permutaciju $P$ i $M$ zadanih intervala odrediš broj inverzija na svakom od njih.

입력

U prvom su retku prirodni brojevi $N$ ($1 ≤ N ≤ 100\,000$) i $M$ ($1 ≤ M ≤ 100\,000$), brojevi iz teksta zadatka.

U drugom retku je $N$ različitih prirodnih brojeva $P_i$ ($1 ≤ P_i ≤ N$).

U sljedećih $M$ redaka su prirodni brojevi $a_i$ i $b_i$ ($1 ≤ a_i ≤ b_i ≤ N$), granice intervala čiji broj inverzija tražimo.

출력

Za svaki od $M$ intervala ispiši broj inverzija permutacije $P$ unutar njega.

예제 입력 1

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

예제 출력 1

0
7
0
4
2

예제 입력 2

5 2
4 3 1 5 2
2 3
1 5

예제 출력 2

1
6

예제 입력 3

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

예제 출력 3

5
0
0

힌트

Opis prvog probnog primjera: Na intervalu od $2$. do $3$. elementa nema inverzija jer je $3<5$. Interval od $1$. do $5$. elementa je zapravo cijeli niz. Inverzije su u tom slučaju parovi elemenata s indeksima $(1, 2)$, $(1, 4)$, $(1, 5)$, $(2, 4)$, $(2, 5)$, $(3, 4)$ i $(3, 5)$.