역전 수 세기 (BIT)

N개의 수 수열에서 역전 쌍(i < j이고 A[i] > A[j])의 수를 구한다. BIT를 이용해 O(N log N)에 해결한다.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 500,000)
둘째 줄에 N개의 정수가 공백으로 구분되어 주어진다. (1 ≤ Ai ≤ N, 중복 없음)

출력

역전 쌍의 수를 출력한다.

예제 입력 1

5
5 3 1 4 2

예제 출력 1

7