37 - 离散化

离散化,把无限空间中有限的个体映射到有限的空间中去,以此提高算法的时空效率。

通俗的说,离散化是在不改变数据相对大小的条件下,对数据进行相应的缩小。例如:

原数据:1,999,100000,15;处理后:1,3,4,2

原数据:{100,200},{20,50000},{1,400}

处理后:{3,4},{2,6},{1,5}
 

有些数据本身很大, 自身无法作为数组的下标保存对应的属性。如果这时只是需要这堆数据的相对属性, 那么可以对其进行离散化处理。当数据只与它们之间的相对大小有关,而与具体是多少无关时,可以进行离散化。

输入

输入第一行包含一个正整数n(1 \le n \le 100000),表示带离散化的数组的大小。

第二行输入n个整数,表示数组中的每一个元素a_i,(0 \le a_i \le 10^9).

输出

输出每个数值离散化后的结果

样例

输入

5
2 4 6 10 8

输出

1 2 3 5 4

输入

7
1 2 2 6 6 6  4

输出

1 2 2 4 4 4 3
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题