Under construction

Still being built. Things may change

Coordinate Compression

Time limit2sMemory limit512 MB

Summary
For each of N coordinates, output the number of distinct values smaller than it, which is its rank under coordinate compression.
Level

Medium4 of 10

Topics
Sorting, Hash map, Array, Binary search
Solved
No attempts yet

Problem

There are NN coordinates X1,X2,…,XNX_1, X_2, \dots, X_N on the number line. We want to apply coordinate compression to these coordinates.

The compressed value Xi′X'_i of XiX_i must equal the number of distinct coordinates XjX_j satisfying Xi>XjX_i > X_j.

Print X1′,X2′,…,XN′X'_1, X'_2, \dots, X'_N, the result of applying coordinate compression to X1,X2,…,XNX_1, X_2, \dots, X_N.

Input

The first line gives NN.

The second line gives X1,X2,…,XNX_1, X_2, \dots, X_N, separated by single spaces.

Output

On the first line, print X1′,X2′,…,XN′X'_1, X'_2, \dots, X'_N, separated by single spaces.

Constraints

  • 1≤N≤1,000,0001 \le N \le 1,000,000
  • −109≤Xi≤109-10^9 \le X_i \le 10^9

Examples2

  1. Example 1

    Input
    5
2 4 -10 4 -9
    Expected output
    2 3 0 3 1

  2. Example 2

    Input
    6
1000 999 1000 999 1000 999
    Expected output
    1 0 1 0 1 0