Description

Given a sequence, please calculate the number of smaller elements at the right of each element.

Note:

• An algorithm with time complexity O(n²) will not pass all the test cases, but it should work for some of them.
• To pass all the test cases, please design an O(nlogn) algorithm.

Input

• Input includes multiple sets of test cases, and each test case consists of two lines.
• The first line contains one integer n.
• The second line includes a n integers sequence
• There won’t be a new line at the end of the file

Note:

1. 1<= n <= 1000000
2. 1 <= value of each element <= 2^30 - 1

Output

• For each test case, print the number of smaller elements which are at the right of each element. For example, given a test case as follows:
  5
  2 8 5 1 7
  The output is: 1 3 1 0 0

This is because 2 has {1}, 8 has {5, 1, 7}, and 5 has {1} which are at the right and smaller than them, respectively, while 1 and 7 do not have any element at their right and smaller than each of them.

• Each output number should be followed by a space.
• Output the ‘\n’ at the end of each test case output.

Sample Input  Download

Sample Output  Download

Tags

Discuss