Insertion Sort Implementation

Insertion Sort Implementation

Implement insertion sort and count the total number of shift operations performed.

Input format

The first line contains N. The second line contains N space-separated integers.

Output format

Print two lines: first the sorted array (space-separated), then the total number of shifts insertion sort performs (each time an element moves one position right while making room — equal to the number of inversions).

Constraints

• Values fit in a 64-bit signed integer
• Trailing whitespace and a trailing newline are ignored by the judge

Read from stdin, write to stdout. Sample cases below show the exact format.

5
4 3 2 10 12

2 3 4 10 12
3

3
1 2 3

1 2 3
0