Problem
Dada una permutación de n elementos.
Responda m consultas sobre el número de inversiones para un subsegmento de permutación de l a r.
Una inversión es un par de índices i, j tales que i < j y a
i > a
j, donde a
i es el i-ésimo elemento de la permutación.
Entrada:
La primera línea contiene el número n (1 <= n <= 10
5).
La segunda línea contiene una permutación de n elementos (los elementos de la permutación son enteros distintos por pares del 1 al n).
La tercera línea contiene el número m (1 <= m <= 10
5).
Las siguientes m líneas contienen dos números enteros l y r: los límites de la consulta (1 <= l, r <= n).
Salida:
Imprima m líneas: las respuestas a estas consultas.
Ejemplos:
| Entrada |
Salida |
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 |