AtCoder Beginner Contest 036

C - 座圧


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

N 人の人が座っています。 i 番目の人の座圧は a_i です。 すぬけ君は、大小関係を保存したまま座圧のデータを圧縮して保存することにしました。 以下の条件を満たす数列 b_1, …, b_N を求めてください。
  • b_i はすべて非負整数である。
  • a_i < a_j ならば b_i < b_j である。
  • a_i = a_j ならば b_i = b_j である。
  • 上の条件を満たす配列のうち、b_i の最大値が最小となる。
このような条件をみたす b は一意に定まることが知られています。

制約

  • 1 ≤ N ≤ 10^5
  • 0 ≤ a_i ≤ 10^9
  • a_i は整数である。

部分点

  • 30 点分のテストケースでは、1 ≤ N ≤ 10^3 をみたす。
  • 上とは別の 30 点分のテストケースでは、0 ≤ a_i ≤ 10^5 をみたす。

入力

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

N
a_1
:
a_N

出力

N 行出力せよ。i 行目には b_i を出力せよ。

入力例1

5
3
3
1
6
1

出力例1

1
1
0
2
0

Submit提出する