Juniorske izborne pripreme 2022. - 1.dan natjecanja - 1.zadatak

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 Pi > Pj.

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 Pi > Pj.

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

Ulazni podaci

U prvom su retku prirodni brojevi N (1 ≤ N ≤ 100000) i M (1 ≤ M ≤ 100000), brojevi iz teksta zadatka. U drugom retku je N različitih prirodnih brojeva Pi (1 ≤ Pi ≤ N). U sljedećih M redaka su prirodni brojevi ai i bi (1 ≤ ai ≤ bi ≤ N), granice intervala čiji broj inverzija tražimo.

Izlazni podaci

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

Bodovanje

U testnim primjerima ukupno vrijednima 20 bodova vrijedit će N, M ≤ 20.

U testnim primjerima ukupno vrijednima 30 bodova vrijedit će N, M ≤ 1000.

Primjer zadatka

Ulaz

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

Izlaz

0
7
0
4
2

Ulaz

5 2
4 3 1 5 2
2 3
1 5

Izlaz

1
6

Ulaz

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

Izlaz

5
0
0