AtCoder-abc036_c
题目描述
有 n 个人排成一列,第 i 个人的座压为 ai。すぬけ君希望在保持大小关系不变的前提下,把这些座压数据压缩后保存。
请构造一个数列 {b1,b2,…,bn},满足以下条件:
1.每个 bi 都是非负整数;
2.若 ai<aj,则 bi<bj;
3.若 ai=aj,则 bi=bj;
4.在所有满足上述条件的数列中,b1,b2,…,bn 中的最大值最小。
可以证明,满足这些条件的数列 b 是唯一的。
输入格式
第一行输入一个整数 n(1≦n≦105) 代表人数。
此后 n 行,第 i 行输入一个整数 ai(0≦ai≦109) 代表第 i 个人的座压。
输出格式
输出 n 行,第 i 行输出一个整数 bi。
测试样例
5
3
3
1
6
1
1
1
0
2
0
样例 1 解释
座压依次为 3,3,1,6,1,其中出现过的不同取值从小到大依次为 1,3,6。
∙把 1 压缩为 0;
∙把 3 压缩为 1;
∙把 6 压缩为 2。
于是得到 b1=1,b2=1,b3=0,b4=2,b5=0。这样既保持了原有的大小关系与相等关系,最大值 2 也已经是所有合法方案中最小的。
6
8
3
8
1
5
3
3
1
3
0
2
1
提示
对于 30 分的测试点,满足 1≦n≦103。
对于另外 30 分的测试点,满足 0≦ai≦105。