Problem
Dada uma permutação de n elementos.
Responda a m consultas sobre o número de inversões para um subsegmento de permutação de l a r.
Uma inversão é um par de índices i, j tal que i < j e a
i > a
j, onde a
i é o i-ésimo elemento da permutação.
Entrada:
A primeira linha contém o número n (1 <= n <= 10
5).
A segunda linha contém uma permutação de n elementos (os elementos da permutação são inteiros distintos emparelhados de 1 a n).
A terceira linha contém o número m (1 <= m <= 10
5).
As próximas m linhas contêm dois inteiros l e r - os limites da consulta (1 <= l, r <= n).
Saída:
Imprima m linhas - as respostas para essas perguntas.
Exemplos:
| Entrada |
Saída |
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 |