F - Numbering Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

長さ N の数列 A が与えられるので、以下の条件を全て満たす数列 B を求めてください。
なお、この数列 B は一意に定まることが示せます。

  • B は (1,2,...,N) を並べ替えて作ることのできる数列である
  • 全ての整数組 (i,j)(i \neq j) について以下を満たす
    • もし A_i<A_j なら、 B_i<B_j
    • もし A_i=A_j かつ i<j なら、 B_i<B_j

制約

  • 入力は全て整数
  • 1 \le N \le 3 \times 10^5
  • 1 \le A_i \le 10^9

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \dots A_N

出力

答えを以下の形式で出力せよ。

B_1 B_2 \dots B_N

入力例 1

10
2 3 4 4 4 4 3 3 2 1

出力例 1

2 4 7 8 9 10 5 6 3 1

数列 A=(2,3,4,4,4,4,3,3,2,1) であるとき、数列 B=(2,4,7,8,9,10,5,6,3,1) です。

入力例 2

1
1000000000

出力例 2

1

入力例 3

20
30 10 40 10 50 90 20 60 50 30 50 80 90 70 90 30 20 30 80 40

出力例 3

5 1 9 2 11 18 3 14 12 6 13 16 19 15 20 7 4 8 17 10

Problem Statement

Given a sequence A of length N, find a sequence B that satisfies all of the following conditions.
We can prove that this sequence B is unique.

  • B is a sequence obtained by rearranging (1,2,...,N).
  • For all integer pairs (i,j)(i \neq j), the following conditions are satisfied:
    • if A_i<A_j, then B_i<B_j;
    • if A_i=A_j and i<j, then B_i<B_j.

Constraints

  • All values in the input are integers.
  • 1 \le N \le 3 \times 10^5
  • 1 \le A_i \le 10^9

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

Print the answer in the following format.

B_1 B_2 \dots B_N

Sample Input 1

10
2 3 4 4 4 4 3 3 2 1

Sample Output 1

2 4 7 8 9 10 5 6 3 1

When the sequence A=(2,3,4,4,4,4,3,3,2,1), the sequence B=(2,4,7,8,9,10,5,6,3,1).

Sample Input 2

1
1000000000

Sample Output 2

1

Sample Input 3

20
30 10 40 10 50 90 20 60 50 30 50 80 90 70 90 30 20 30 80 40

Sample Output 3

5 1 9 2 11 18 3 14 12 6 13 16 19 15 20 7 4 8 17 10