Ordenação por mesclagem com contagem de inversões

TypeScript Hard sorting

Tarefa «Ordenação por mesclagem com contagem de inversões»

Dado um array de números inteiros. É necessário ordená-lo em ordem crescente usando ordenação por mesclagem, e também contar o número de inversões no array original. Uma inversão é um par de índices (i, j) tal que i < j e a[i] > a[j]. Dados de entrada: a primeira linha contém o número n (1 ≤ n ≤ 10^5), a segunda linha contém n números inteiros, cada um em módulo não excedendo 10^9. Dados de saída: a primeira linha — o número de inversões, a segunda linha — o array ordenado separado por espaços.

Formato de Entrada

Primeiro um número inteiro n. Em seguida, n números inteiros separados por espaços.

Formato de Saída

Duas linhas: a primeira — o número de inversões (um número inteiro), a segunda — o array ordenado separado por espaços.

Exemplos

Exemplo 1

ENTRADA

5
3 1 4 2 5

SAÍDA

3
1 2 3 4 5

Exemplo 2

ENTRADA

4
4 3 2 1

SAÍDA

6
1 2 3 4

Exemplo 3

ENTRADA

123

SAÍDA

0

Exemplo 4

ENTRADA

0

SAÍDA

0

main.ts