Description

In this homework, you are asked to implement 2 functions.

1. Inversion pairs count

2. Radix sort(LSD) process

 

Inversion pair

Let A be a sequence of numbers. (i, j) is an inversion pair if i < j but A[i] > A[j].

For example: A = [1, 2, 3, 4], then A has no inversion pair.

For example: B = [4, 3, 2, 1], B has 6 inversion pairs: (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4).

Inversion pairs count

Output the number of inversion pairs

For example: A = [9, 4, 5, 3], the output is 5. Because A has inversion pairs: (1, 2), (1, 3), (1, 4), (2, 4), (3, 4).

Radix sort(LSD) process

Output first element and last element of results in every pass of the radix sort(LSD).

 

You are allowed to use STL.

But don't use any STL related to sort.

Input

There are multiple testcases, and each testcase begins with a line containing two integers n and r, the number of elements in sequence and the radix.

The next line includes the n integers in the sequence.

Please note:

1) 1 <= the number of elements <= 1000000

2) 2 <= radix <= 1000

3) 1 <= value of each element <= 2³¹ - 1

    (each value is decimal integer)

Output

For each input, output the following results separated by a newline symbol.

• Inversion pairs count
• First element and last element of results in every pass of the radix sort(LSD)  

          (output of every pass separated by a newline symbol too)

 

Sample Input  Download

Sample Output  Download

Tags

Discuss