Contagem de Inversões
Era uma vez, em uma terra mística, que vivia um sábio feiticeiro chamado Merlin. Merlin possuía um poder único para perceber os padrões ocultos em permutações. Ele era particularmente fascinado pelo conceito de inversões em uma permutação.
Uma inversão em uma permutação é um par de elementos
(a_i, a_j) em que i < j e a_i > a_j. O número de inversões em uma permutação indica o quão distante ela está de estar ordenada em ordem crescente.Merlin decidiu desafiar os talentosos programadores com o seguinte problema: Dada uma permutação de inteiros de
1 até n, a sua tarefa é calcular o número de inversões presentes nessa permutação.Entrada
A primeira linha contém um único inteiro
n (1 ≤ n ≤ 100 000), que representa o tamanho da permutação. A segunda linha contém n inteiros separados por espaços, representando os elementos da permutação.Saída
Imprima um único inteiro, que representa o número de inversões na permutação fornecida.
Exemplos
Entrada | Saída |
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