====== 달리기 ======

===== 풀이 =====
  * [[ps:Inversion Counting]]을 응용한 문제. 
  * inversion관계에 있는 (i,j) 갯수의 총합을 구하는 것이 아니라, 각 j별로 갯수를 구해주면 된다.
  * [[ps:Inversion Counting]]에 설명했듯이, 머지소트를 응용한 방식과 Order Statistic Tree를 이용한 방식 모두 가능하지만, Order Statistic Tree를 사용한 방식이 더 빨라서 이쪽만 코드를 수록했다.
    * 좌표압축을 추가로 해줘야 하는 페널티가 있음에도, Order Statistic Tree는 약 3600ms로 머지소트 방식의 약 4000ms보다 빨랐다
  * 시간 복잡도는 O(nlogn)이다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 2517. 달리기".

- Problem link: https://www.acmicpc.net/problem/2517
- Solution link: http://www.teferi.net/ps/problems/boj/2517
"""

import sys
from teflib import fenwicktree


def main():
    N = int(sys.stdin.readline())
    speeds = [int(sys.stdin.readline()) for _ in range(N)]

    ost = fenwicktree.OrderStatisticTree(N)
    rank_by_speed = {x: i for i, x in enumerate(sorted(speeds, reverse=True))}
    for speed in speeds:
        rank = rank_by_speed[speed]
        print(ost.count_less_than(rank) + 1)
        ost.add(rank)


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:fenwicktree#OrderStatisticTree|teflib.fenwicktree.OrderStatisticTree]]

{{tag>BOJ ps:problems:boj:플래티넘_4}}