버블 정렬의 맞교환 횟수

N개의 정수로 이루어진 수열 A[1], A[2], ..., A[N]이 주어진다. 이 수열을 버블 정렬로 오름차순 정렬할 때, 인접한 두 원소를 맞교환하는 횟수를 구하라.

버블 정렬은 인접한 두 원소를 비교하여 순서가 잘못되어 있으면 서로 바꾸는 과정을 반복해 수열을 정렬한다. 예를 들어 수열 3 2 1은 2 3 1, 이어서 2 1 3, 마지막으로 1 2 3이 되므로 맞교환이 총 3번 발생한다.

첫째 줄에 정수 N (1 <= N <= 500,000)이 주어진다.

둘째 줄에 N개의 정수 A[1], A[2], ..., A[N]이 주어진다. 각 값은 0 <= |A[i]| <= 1,000,000,000을 만족한다.

수열을 오름차순으로 정렬하기 위해 버블 정렬에서 발생하는 인접 맞교환 횟수를 출력한다.