====== 버블 소트 ======

===== 풀이 =====
  * 말을 살짝 꼬아놨지만 결국은 [[ps:Inversion Counting|Inversion의 갯수를 세는 문제]]
  * [[ps:Inversion Counting]]에서 설명했듯, 머지소트에 기반한 방식과 Order Statistic Tree에 기반한 방식으로 풀 수 있다.
  * 문제가 여기에서 조금 확장되면 머지소트을 사용하는 방법은 적용하기가 어렵거나 속도가 느리거나 하지만, 이 문제에서만은 머지소트 방법이 더 빠르게 동작했다.  
  * 그래서 두가지 코드를 모두 적었다. 시간 복잡도는 둘 다 O(nlogn).

===== 코드 =====
==== 코드 1 - 머지소트 ====
<dkpr py>
"""Solution code for "BOJ 1517. 버블 소트".

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


def sort_and_count_inversion(list_):
    if len(list_) <= 1:
        return 0
    mid = len(list_) // 2
    left, right = list_[:mid], list_[mid:]
    inversion_count = (sort_and_count_inversion(left)
                       + sort_and_count_inversion(right))
    l_size, r_size = mid, len(right)
    i = j = 0
    ret = []
    while True:
        try:
            if left[i] <= right[j]:
                ret.append(left[i])
                i += 1
            else:
                ret.append(right[j])
                j += 1
                inversion_count += l_size - i
        except IndexError:
            break            
    list_[:] = ret
    list_.extend(left[i:])
    list_.extend(right[j:])
    return inversion_count


def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    print(sort_and_count_inversion(A))


if __name__ == '__main__':
    main()
</dkpr>

==== 코드 2 - Order Statistic Tree ====
<dkpr py>
"""Solution code for "BOJ 1517. 버블 소트".

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

from teflib import fenwicktree


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    
    compress_map = {x: i for i, x in enumerate(sorted(set(A)))}
    comp_a = [compress_map[x] for x in A]
    ost = fenwicktree.OrderStatisticTree(len(compress_map))
    answer = 0
    for a_i in reversed(comp_a):
        answer += ost.count_less_than(a_i)
        ost.add(a_i)
        
    print(answer)


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

{{tag>BOJ ps:problems:boj:골드_1}}