AT_past202309_d 相対評価のスコア

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 $ .

The input is given from Standard Input in the following format: > $ N $ $ A _ 1 $ $ A _ 2 $ $ \ldots $ $ A _ N $

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 Explanation 1 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 $ . ### Constraints - $ 1\leq N\leq10^5 $ - $ 1\leq A _ i\leq10^9 (1\leq i\leq N) $ - All input values are integers.