/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
問題文
あなたは、プログラミングコンテストを主催しました。 コンテストには N 人が参加し、i (1\leq i\leq N) 番目の参加者は A _ i 点を得ました。
あなたは、全員のスコアを 0 以上 10^9 以下の整数にするために、i=1,2,\ldots,N について次の式で i 番目の参加者の相対スコアを計算することにしました。
- \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 は A _ i のうちすべての整数 j (1\leq j\leq N) について A _ j\leq A _ i を満たすようなものを表し、\operatorname{round}(x) は n-\dfrac12\leq x\lt n+\dfrac12 を満たす唯一の整数 n を表します。
i=1,2,\ldots,N について、i 番目の参加者の相対スコアを計算してください。
制約
- 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 行に出力せよ。
入力例 1
3 200 600 300
出力例 1
333333333 1000000000 500000000
それぞれの参加者の相対スコアは、以下のように計算されます。
A _ 1\leq A _ 2,A _ 2\leq A _ 2,A _ 3\leq A _ 2 が成り立つので、 \max _ iA _ i=A _ 2=600 です。
- 1 番目の参加者の得点は A _ 1=200 点です。10^9\times\dfrac{200}{600}=\dfrac{10^9}3 で、333333333-\dfrac12\leq\dfrac{10^9}3\lt333333333+\dfrac12 なので、1 番目の参加者の相対スコアは 333333333 です。
- 2 番目の参加者の得点は A _ 2=600 点です。10^9\times\dfrac{600}{600}=10^9 で、1000000000-\dfrac12\leq10^9\lt1000000000+\dfrac12 なので、2 番目の参加者の相対スコアは 1000000000 です。
- 3 番目の参加者の得点は A _ 3=300 点です。10^9\times\dfrac{300}{600}=5\times10^8 で、500000000-\dfrac12\leq5\times10^8\lt500000000+\dfrac12 なので、3 番目の参加者の相対スコアは 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
Problem Statement
You held a programming contest. There were N participants, and the i-th (1\leq i\leq N) of them scored A _ i points.
In order to make their scores integers between 0 and 10^9 (inclusive), you are going to determine the relative score of the i-th participant for each i=1,2,\ldots,N by the following expression:
- \operatorname{round}\left(10^9\times\dfrac{A _ i}{\max _ iA _ i}\right).
Here, \max _ iA _ i denotes the maximum value among A _ i, and \operatorname{round}(x) denotes x rounded off to an integer. Formally, \max _ iA _ i is A _ i that satisfies A _ j\leq A _ i for all j (1\leq j\leq N), and \operatorname{round}(x) is the unique integer n satisfying n-\dfrac12\leq x\lt n+\dfrac12.
Find the relative score of the i-th participant for i=1,2,\ldots,N.
Constraints
- 1\leq N\leq10^5
- 1\leq A _ i\leq10^9 (1\leq i\leq N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A _ 1 A _ 2 \ldots A _ N
Output
Print the relative scores of the i-th participants (1\leq i\leq N) in ascending order of i, separated by spaces in a single line.
Sample Input 1
3 200 600 300
Sample Output 1
333333333 1000000000 500000000
The relative score of each participant is computed as follows.
\max _ iA _ i=A _ 2=600, since A _ 1\leq A _ 2,A _ 2\leq A _ 2, and A _ 3\leq A _ 2.
- The 1-st participant scored A _ 1=200 points. 10^9\times\dfrac{200}{600}=\dfrac{10^9}3 and 333333333-\dfrac12\leq\dfrac{10^9}3\lt333333333+\dfrac12, so the relative score of the 1-st participant is 333333333.
- The 2-nd participant scored A _ 2=600 points. 10^9\times\dfrac{600}{600}=10^9 and 1000000000-\dfrac12\leq10^9\lt1000000000+\dfrac12, so the relative score of the 2-nd participant is 1000000000.
- The 3-rd participant scored A _ 3=300 points. 10^9\times\dfrac{300}{600}=5\times10^8 and 500000000-\dfrac12\leq5\times10^8\lt500000000+\dfrac12, so the relative score of the 3-rd participant is 500000000.
Sample Input 2
2 1 999999999
Sample Output 2
1 1000000000
Sample Input 3
10 55580908 183811851 247188750 266233976 335843599 344138315 389659771 389921297 698238479 720357617
Sample Output 3
77157382 255167498 343147270 369585841 466217877 477732597 540925454 541288504 969294226 1000000000