EN
RU
ES
ZH
FR
DE
PT
AR
HI
Merge sort with inversion counting
TypeScript
Hard
sorting
Task «Merge sort with inversion counting»
Given an array of integers, it is necessary to sort it in ascending order using merge sort, and also to count the number of inversions in the original array. An inversion is a pair of indices (i, j) such that i < j and a[i] > a[j]. Input data: the first line contains the number n (1 ≤ n ≤ 10^5), the second line contains n integers, each not exceeding 10^9 in absolute value. Output data: the first line is the number of inversions, the second line is the sorted array separated by spaces.
Input Format
First, an integer n. Then n integers separated by spaces.
Output Format
Two strings: the first is the number of inversions (an integer), the second is a sorted array separated by spaces.
Examples
Example 1
INPUT
5
3 1 4 2 5
OUTPUT
3
1 2 3 4 5
Example 2
INPUT
4
4 3 2 1
OUTPUT
6
1 2 3 4
Example 3
INPUT
123
OUTPUT
0
Example 4
INPUT
0
OUTPUT
0
main.ts