Сортировка слиянием с подсчетом инверсий

TypeScript Сложный sorting

Задача «Сортировка слиянием с подсчетом инверсий»

Дан массив целых чисел. Необходимо отсортировать его по возрастанию с помощью сортировки слиянием, а также подсчитать количество инверсий в исходном массиве. Инверсией называется пара индексов (i, j), такая что i < j и a[i] > a[j]. Входные данные: первая строка содержит число n (1 ≤ n ≤ 10^5), вторая строка содержит n целых чисел, каждое по модулю не превышает 10^9. Выходные данные: первая строка — количество инверсий, вторая строка — отсортированный массив через пробел.

Формат ввода

Сначала целое число n. Затем n целых чисел через пробел.

Формат вывода

Две строки: первая — количество инверсий (целое число), вторая — отсортированный массив через пробел.

Примеры

Пример 1

ВВОД

5
3 1 4 2 5

ВЫВОД

3
1 2 3 4 5

Пример 2

ВВОД

4
4 3 2 1

ВЫВОД

6
1 2 3 4

Пример 3

ВВОД

123

ВЫВОД

0

Пример 4

ВВОД

0

ВЫВОД

0

main.ts