Inverzije

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.

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)$.