Smaller To The Right Counts

HardSortingMerge-SortFenwick-TreeInversions5 hidden tests

A sequence of n values is given. For every position i, count how many positions j with j > i have value[j] < value[i] (strictly smaller). Output all n counts in the original order.

Input format

Line 1: an integer n. Line 2: n space-separated integers, the values.

Output format

n space-separated integers on one line: for each position (in order), the number of strictly smaller values to its right.

Constraints

1 ≤ n ≤ 100000
-1000000000 ≤ value ≤ 1000000000

Examples

Example 1

Input

5
5 2 6 1 3

Expected

3 1 2 0 0

Explanation

To the right of 5 the smaller values are 2,1,3 -> 3. Right of 2: only 1 -> 1. Right of 6: 1,3 -> 2. Right of 1: none. Right of 3: none. Output: 3 1 2 0 0.

Example 2

Input

3
1 2 3

Expected

0 0 0

Explanation

The values increase, so nothing to the right is smaller: 0 0 0.

Ready to solve this?

Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.

Sign in to solve →