Bubble Sort Swap Count

You are given a sequence A[1], A[2], ..., A[N] of N integers. Determine how many adjacent swaps occur when the sequence is sorted in nondecreasing order by bubble sort.

Bubble sort repeatedly compares adjacent elements and swaps them when they are in the wrong order. For instance, the sequence 3 2 1 becomes 2 3 1, then 2 1 3, and finally 1 2 3, so three adjacent swaps occur.

The first line contains an integer N (1 <= N <= 500,000).

The second line contains N integers A[1], A[2], ..., A[N]. Each value satisfies 0 <= |A[i]| <= 1,000,000,000.

Print the number of adjacent swaps performed by bubble sort to sort the sequence in nondecreasing order.