Problem
Data una permutazione di n elementi.
Rispondi a m domande sul numero di inversioni per un sottosegmento di permutazione da l a r.
Un'inversione è una coppia di indici i, j tali che i < j e a
i > a
j, dove a
i è l'i-esimo elemento della permutazione.
Inserimento:
La prima riga contiene il numero n (1 <= n <= 10
5).
La seconda riga contiene una permutazione di n elementi (gli elementi della permutazione sono numeri interi distinti a coppie da 1 a n).
La terza riga contiene il numero m (1 <= m <= 10
5).
Le m righe successive contengono due numeri interi l e r - i limiti della query (1 <= l, r <= n).
Uscita:
Stampa m righe - le risposte a queste domande.
Esempi:
| Input |
Uscita |
5
4 5 2 3 1
3
1 3
3 5
15 |
2
2
8 |
6
5 2 4 3 1 6
3
46
25
15 |
1
4
8 |