Rank Transform

Difficulty: 1300 3000 ms 128 MB

sorting

Replace each value by its rank: the smallest distinct value becomes 1, the next 2, and so on (equal values share a rank).

Input: the first line has N; the second line has N integers.

Output: the N ranks in the original order.

Constraints:

• 1 ≤ N ≤ 10⁵
• −10⁹ ≤ a_i ≤ 10⁹

Sample Tests

5
40 10 20 20 30

4 1 2 2 3

1
-5

1

Read the Editorial