问题陈述
您举办了一场编程竞赛。有 N 参与者,以及 i-th (1\leq i\leq N) 其中得分 A _ i 点。
为了使他们的分数介于 0 和 10^9 (含),您将确定的相对分数 i每个参与者的第 i=1,2,\ldots,N 通过以下表达式:
- \operatorname{round}\left(10^9\times\dfrac{A _ i}{\max _ iA _ i}\right).
在这里, \max _ iA _ i 表示其中的最大值 A _ i,和 \operatorname{round}(x) 表示 x 四舍五入为整数。 正式地, \max _ iA _ i is A _ i 满足 A _ j\leq A _ i 对于所有人 j (1\leq j\leq N),和 \operatorname{round}(x) 是唯一的整数 n 满意 n-\dfrac12\leq x\lt n+\dfrac12.
查找的相对分数 i第 参与者 i=1,2,\ldots,N.
约束
- 1\leq N\leq10^5
- 1\leq A _ i\leq10^9 (1\leq i\leq N)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A _ 1 A _ 2 \ldots A _ N
输出
打印相对分数 i第参与者 (1\leq i\leq N) 按升序排列 i,在一行中用空格分隔。
示例输入 1
3 200 600 300
示例输出 1
333333333 1000000000 500000000
每个参与者的相对分数计算如下。
\max _ iA _ i=A _ 2=600,因为 A _ 1\leq A _ 2,A _ 2\leq A _ 2,和 A _ 3\leq A _ 2.
- 的 1-st 参与者得分 A _ 1=200 点。 10^9\times\dfrac{200}{600}=\dfrac{10^9}3 和 333333333-\dfrac12\leq\dfrac{10^9}3\lt333333333+\dfrac12,所以相对分数 1-st 参与者是 333333333.
- 的 2-nd 参与者得分 A _ 2=600 点。 10^9\times\dfrac{600}{600}=10^9 和 1000000000-\dfrac12\leq10^9\lt1000000000+\dfrac12,所以相对分数 2-nd 参与者是 1000000000.
- 的 3-rd 参与者得分 A _ 3=300 点。 10^9\times\dfrac{300}{600}=5\times10^8 和 500000000-\dfrac12\leq5\times10^8\lt500000000+\dfrac12,所以相对分数 3-rd 参与者是 500000000.
示例输入 2
2 1 999999999
示例输出 2
1 1000000000
示例输入 3
10 55580908 183811851 247188750 266233976 335843599 344138315 389659771 389921297 698238479 720357617
示例输出 3
77157382 255167498 343147270 369585841 466217877 477732597 540925454 541288504 969294226 1000000000