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