| Author: | Евгений Татаринов | Time limit: | 1 sec | |
| Input file: | Standard input | Memory limit: | 256 Mb | |
| Output file: | Standard output |
Once upon a time, Eugene and Angelica found themselves at a javelin throwing competition as spectators. N athletes were participating in the competition.
Each time the i-th athlete threw the javelin, Eugene would inform Angelica about the distance the athlete threw the javelin (it happened that all the numbers Eugene mentioned were pairwise distinct). At the same time, Angelica recorded on a piece of paper the place that the i-th athlete would take after their throw.
Unfortunately, when the competition ended, Angelica lost the sheet of paper and was very upset. But Eugene remembers how many meters each athlete threw their javelin. Help the kids restore the lost sheet!
The first line of input contains a natural number N — the number of athletes.
The second line contains a sequence of distinct natural numbers L, where Li — is the number indicating how many meters the i-th athlete threw their javelin.
In a single line, output a sequence of N natural numbers, where the i-th number indicates the place that the i-th athlete takes after their throw.
1 ≤ N ≤ 105, 1 ≤ Li ≤ 109
The first athlete threw the javelin and became the first in the list. The second athlete threw the javelin farther than the first and became the first in the list. The third athlete threw farther than the first but closer than the second, so the third became the second in the list. The fourth athlete threw farther than the first but closer than the second and the third, so the fourth became the third in the list.
| No. | Standard input | Standard output |
|---|---|---|
| 1 | |
|
Пусть какой-то спортсмен кидает копье, тогда номер его места в списке будет равен количеству копьев, пролетевших не меньше его копья.
Создадим массив L, где Ld равно 1, если какой-либо спортсмен кинул копье на расстояние, равно d метров, в противном случае Ld равно 0. Заметим, что нам неважно, насколько далеко кинул копье каждый из спортсменов, нам важно только то, кто дальше кого кинул. Тогда сожмем координаты, и теперь 1 ≤ d ≤ n.
Переберем всех спортсменов по порядку. Пусть i-ый спортсмен кинул на m ≤ n метров. Обновим Ld, теперь Ld = 1. Тогда место, которое он занял, равно Ld + Ld + 1 + ... + Ln. Данную сумму можно искать, к примеру, с помощью дерева отрезков или дерева Фенвика.