← 返回题目列表

AtCoder · tessoku_book_o

A15. 压缩

中文机器翻译题面 查看原题

配点: 1000 点

問題文

配列 A = [A_1, A_2, \cdots, A_N] 。尽可能压缩数组以保持大小关系。

这里,压缩是指满足以下所有条件的数组。 这是查找 B = [B_1, B_2, \cdots, B_N] 的操作。注意这样的数组 B 可以用一种方式确定。

  • 条件1 B_1, B_2, \cdots, B_N 是大于或等于 1 的整数。 一组使得
  • 条件2 A_i < A_j 对于 (i, j) ,B_i < B_j 。
  • 条件3 A_i = A_j 对于 (i, j) ,B_i = B_j 。
  • 条件4 A_i > A_j 对于 (i, j) ,B_i > B_j 。
  • 条件5 当满足条件 1 至 4 时,数组 尽可能减小 B 的最大值。 请输出

制約

  • 1 \leq N \leq 100\,000
  • 1 \leq A_i \leq 10^9

入力

输入是按以下格式从标准输入给出的。

N
A_1 A_2 \cdots A_N

出力

整数 B_1, B_2, \cdots, B_N ,以空格分隔。 在不破坏大小关系的情况下压缩


入力例 1

5
46 80 11 77 46

出力例 1

2 4 1 3 2

A = [46, 80, 11, 77, 46] 时,B = [2, 4, 1, 3, 2] 。