Para efeitos da nota atribuida à resolução de exercícios ao longo do semestre - Submeter até 23:59 de 5 de Junho
(o problema continuará depois disponível para submissão, mas sem contar para a nota)
[para perceber o contexto do problema deve ler o guião da aula #11]
O número de inversões de um array indica o quão longe (ou
perto) ele está de ficar ordenado. Um array completamente ordenado (de
forma crescente) tem um número de inversões igual a zero. Se o array
está ordenado mas de forma inversa (de forma decrescente) então o
número de inversões é máximo.
De uma fora mais formal, dois elementos v[i] e v[j] estão invertidos se v[i]>v[j] e i<j. Por exemplo, a sequência (4,3,1,2) tem 5 inversões: (4,3), (4,1), (4,2), (3,1) e (3,2).
Dada uma sequência de números, calcular o seu número de inversões.
Na primeira linha do input vem um número N (1 ≤ N ≤ 50 000) que corresponde à quantidade de números a considerar.
Segue-se uma linha contendo os números a considerar, separados por um único espaço. É garantido que todos os números são inteiros positivos menores que um milhão.
O output deve ser constituído por uma única linha contendo um número: a quantidade de inversões.
4 4 3 1 2
5
Estruturas de Dados (CC1007)
DCC/FCUP - Faculdade de Ciências da Universidade do Porto