Conteo de Inversiones
Había una vez, en una tierra mística, un sabio hechicero llamado Merlín. Merlín poseía un poder único para percibir los patrones ocultos en las permutaciones. Sentía especial fascinación por el concepto de inversiones dentro de una permutación.
Una inversión en una permutación es un par de elementos
($$a_i, a_j$$) tal que i < j y . El número de inversiones en una permutación indica cuánto se aleja dicha permutación de un orden ascendente.Merlín decidió lanzar un reto a los programadores talentosos proponiendo el siguiente problema: Dada una permutación de enteros que van de
1 a n, se debe calcular el número de inversiones presentes en la permutación.Entrada
La primera línea contiene un único entero
n (1 ≤ n ≤ 100 000), que representa el tamaño de la permutación. La segunda línea contiene n números separados por espacios, que representan los elementos de la permutación.Salida
Imprime un solo número entero, que sea la cantidad de inversiones de la permutación dada.
Ejemplos
Entrada | Salida |
5
3 1 4 2 5 | 3 |
4
1 2 3 4 | 0 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB