10053 병합 정렬 카운트 Gold V

문제

N개의 정수가 주어졌을 때, 병합 정렬(Merge Sort)을 수행하면서 발생하는 역전(inversion)의 수를 구하는 프로그램을 작성하시오.

역전이란 i < j이면서 A[i] > A[j]인 쌍 (i, j)의 개수를 의미한다.

입력

첫째 줄에 정수의 개수 N (1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에 N개의 정수가 공백으로 구분되어 주어진다. 각 정수는 절댓값이 1,000,000,000 이하이다.

출력

역전의 수를 출력한다.

5
3 1 5 2 4

4