Problem:
The Number of Inversions For a given sequence $A = \{a_0, a_1, ... a_{n-1}\}$, the number of pairs $(i, j)$ where $a_i > a_j$ and $i < j$, is called the number of inversions. The number of inversions is equal to the number of swaps of Bubble Sort defined in the following program: bubbleSort(A)
  cnt = 0 // the number of inversions
  for i = 0 to A.length-1
    for j = A.length-1 downto i+1
      if A[j] < A[j-1]
	swap(A[j], A[j-1])
	cnt++

  return cnt For the given sequence $A$, print the number of inversions of $A$. Note that you should not use the above program, which brings Time Limit Exceeded. Input In the first line, an integer $n$, the number of elements in $A$, is given. In the second line, the elements $a_i$ ($i = 0, 1, .. n-1$) are given separated by space characters. output Print the number of inversions in a line. Constraints  $ 1 \leq n \leq 200,000$  $ 0 \leq a_i \leq 10^9$  $a_i$ are all different  Sample Input 1 5
3 5 2 1 4 Sample Output 1 6 Sample Input 2 3
3 1 2 Sample Output 2 2

Solution (Python):
def div(A, l, r):
    if l+1 < r:
        mid = (l+r) // 2
        div(A, l, mid)
        div(A, mid, r)
        solve(A, l, mid, r)

def solve(A, l, m, r):
    global cnt
    l_i = 0
    r_i = 0
    L = A[l:m]
    R = A[m:r]
    L.append(1e9)
    R.append(1e9)
    for i in range(l, r):
        if L[l_i] > R[r_i]:
            A[i] = R[r_i]
            r_i += 1
        else:
            A[i] = L[l_i]
            l_i += 1
            cnt += r_i
n = int(input())
A = list(map(int, input().split()))
cnt = 0
div(A, 0, n)
print(cnt)

Solution (Python):
def inv(A,l,m,r):
    global c
    L,R=A[l:m]+[1e9],A[m:r]+[1e9]
    i=j=0
    for k in range(l,r):
        if L[i]<R[j]:
            A[k]=L[i];i+=1;c+=j
        else:
            A[k]=R[j];j+=1
def s(A,l,r):
 if l+1<r:
    m=(l+r)//2;s(A,l,m);s(A,m,r);inv(A,l,m,r)
c=0
n=int(input())
A=[int(i) for i in input().rstrip().split(" ")]
s(A,0,n)
print(c)

Solution (Python):



def merge(a, left, mid, right):
    L = a[left:mid] + [INF]
    R = a[mid:right] + [INF]
    
       
    i = 0
    j = 0
    for k in range(left, right):
     
        global idx
        
        if( L[i] <= R[j] ):
            a[k] = L[i]
            i += 1
        else:
            a[k] = R[j]
            j += 1
            idx += mid - left - i

def merge_sort(a, left, right):
    if( left + 1 < right ):
        mid = (left + right) // 2 
        merge_sort(a, left, mid)
        merge_sort(a, mid, right)
        merge(a, left, mid, right)


INF = 1000000000
idx = 0
n = int(input())
a = [int(i) for i in input().split()]
merge_sort(a,0,len(a))
print(idx)

Solution (Python):
infinity=2**35
def merge(A,left,mid,right):
  global cnt

  L=A[left:mid]
  R=A[mid:right]
  L.append(infinity)
  R.append(infinity)

  i=0
  j=0

  inver=0

  for k in range(left,right):
    if L[i]<=R[j]:
      A[k]=L[i]
      i+=1
      if inver>0:
        cnt+=inver
      
    else:
      A[k]=R[j]
      j+=1
      inver+=1



def mergeSort(A,left,right):
  if (left+1)<right:
    mid=(left+right)//2
    mergeSort(A,left,mid)
    mergeSort(A,mid,right)
    merge(A,left,mid,right)


n=int(input())
A=list(map(int,input().split()))
cnt=0

mergeSort(A,0,n)

print(cnt)

Solution (Python):
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    cnt = 0

    def merge(A, l, mid, r):
        nonlocal cnt
        n1 = mid - l
        n2 = r - mid
        L = [A[l + i] for i in range(n1)]
        R = [A[mid + i] for i in range(n2)]
        L.append(1 << 60)
        R.append(1 << 60)
        i = 0
        j = 0
        for k in range(l, r):
            if L[i] <= R[j]:
                A[k] = L[i]
                i = i + 1
            else:
                cnt += n1 - i
                A[k] = R[j]
                j = j + 1

    def merge_sort(A, left, right):
        if len(A) == 1:
            return
        if left+1 < right:
            mid = (left + right) // 2
            merge_sort(A, left, mid)
            merge_sort(A, mid, right)
            merge(A, left, mid, right)

    merge_sort(A, 0, N)

    print(cnt)


if __name__ == '__main__':
    main()

Solution (Python):
import math




n=int(input())
A=list(map(int,input().split()))
def merge(A,left,mid,right):
    global count
    L=A[left:mid]+[math.inf]
    R=A[mid:right]+[math.inf]
    i,j=0,0
    for k in range(left,right):
        if L[i]<R[j]:
            A[k]=L[i]
            i+=1
        else:
            A[k]=R[j]
            j+=1
            count+=len(L)-1-i


    
            
def mergeSort(A,left,right):
    if left+1<right:
        
        mid=(left+right)//2
        mergeSort(A,left,mid)
        mergeSort(A,mid,right)
        merge(A,left,mid,right)
count=0
mergeSort(A,0,n)
print(count)

Solution (Python):
global count


def merge(arr, l, mid, r):
    arr_copy = list(arr[l:r + 1])
    global count
    l_idx, r_idx = l, mid + 1
    for i in range(l, r + 1):
        if l_idx > mid:
            arr[i] = arr_copy[r_idx - l]
            r_idx += 1
        elif r_idx > r:
            arr[i] = arr_copy[l_idx - l]
            l_idx += 1
        elif arr_copy[l_idx - l] <= arr_copy[r_idx - l]:
            arr[i] = arr_copy[l_idx - l]
            l_idx += 1
        else:
            arr[i] = arr_copy[r_idx - l]
            count += mid - l_idx + 1
            r_idx += 1


def merge_sort(arr, l, r):
    if l >= r:
        return
    mid = (l + r) // 2
    merge_sort(arr, l, mid)
    merge_sort(arr, mid + 1, r)
    merge(arr, l, mid, r)


if __name__ == '__main__':
    n = int(input())
    arr = list(map(int, input().split()))
    count = 0
    merge_sort(arr, 0, n - 1)
    print(count)

Solution (Python):
num = 0
def marge_sort(array):
    global num
    if len(array) < 2: return array
    
    mid = len(array) // 2
    left = marge_sort(array[:mid])
    right = marge_sort(array[mid:])
    
    len_l, len_r = len(left), len(right)
    left += [float("inf")]
    right += [float("inf")]
    
    marray = [0] * (len_l + len_r)
            
    l, r = 0, 0
    for i in range(len_l + len_r):
        if left[l] <= right[r]:
            marray[i] = left[l]
            l += 1
            num += r
        else:
            marray[i] = right[r]
            r += 1

    return marray

n = int(input())
a = list(map(int, input().split()))

marge_sort(a)
print(num)

Solution (Python):
def merge(A, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid] + [INF]
    R = A[mid:right] + [INF]
    i = 0
    j = 0
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
            cnt += mid - left - i

def mergeSort(A, left, right):
    if left + 1 < right:
        mid = (left + right)//2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)

INF = 10000000000
n = int(input())
A = list(map(int,input().split()))
cnt = 0
mergeSort(A,0,n)
print(cnt)

Solution (Python):
def merge(A,left,mid,right):
    L=A[left:mid]+[float("INF")]
    R=A[mid:right+1]+[float("INF")]
    i=0
    j=0
    global cnt
    for k in range(left,right+1):
        if L[i]<=R[j]:
            A[k]=L[i]
            i+=1
        else:
            A[k]=R[j]
            j+=1
            cnt+=len(L)-i-1
def mergeSort(A,left,right):
    if left<right:
        mid=(left+right)//2+1
        mergeSort(A,left,mid-1)
        mergeSort(A,mid,right)
        merge(A,left,mid,right)
n=int(input())
S=list(map(int,input().split()))
cnt=0
mergeSort(S,0,n-1)
print(cnt)

Solution (Python):
n = int(input())
A = list(map(int, input().split()))

class Inversion():
    def __init__(self):
        self.cnt = 0
    def merge(self, A, left, mid, right):
        n1 = mid - left 
        n2 = right - mid
        L = [0] * (n1 + 1)
        R = [0] * (n2 + 1)
        for i in range(n1):
            L[i] = A[left + i]
        for i in range(n2):
            R[i] = A[mid + i]
        L[n1] = 10000000000
        R[n2] = 10000000000
        i = 0
        j = 0
        for k in range(left, right):
            if L[i] <= R[j]:
                A[k] = L[i]
                i += 1
            else:
                self.cnt += n1 - i
                A[k] = R[j]
                j += 1
        return self
    
    def mergesort(self, A, left, right):
        if left + 1 < right:
            mid = (left + right) // 2
            self.mergesort(A, left, mid)
            self.mergesort(A, mid, right)
            self.merge(A, left, mid, right)
        return self

a = Inversion().mergesort(A, 0, n)
print(a.cnt)

Solution (Python):





INF = 10**9 + 1


def merge(A: list, left: int, mid: int, right: int) -> int:
    '''
    2つの配列をmergeする関数

    Aはこのプログラムで処理する配列。
    left, mid, rightはAのindex。
    '''
    cnt = 0  
    n1 = mid-left  
    

    L = A[left:mid]  
    L.append(INF)  
    R = A[mid:right]
    R.append(INF)  

    i_l, i_r = 0, 0  
    for k in range(left, right):
        
        if L[i_l] <= R[i_r]:
            A[k] = L[i_l]
            i_l += 1
        else:
            A[k] = R[i_r]
            i_r += 1
            cnt += n1-i_l  
    return cnt


def merge_sort(A: list, left: int, right: int):
    '''
    マージソートをしつつ、反転数を再帰的に計算する。

    ここではマージを再帰的に適応し反転数をどんどん上に伝播させていく仕組み
    '''
    if left + 1 >= right:  
        return 0

    mid = (left+right)//2
    v1 = merge_sort(A, left, mid)  
    v2 = merge_sort(A, mid, right)
    v3 = merge(A, left, mid, right)  

    return v1+v2+v3


n = int(input())
A = list(map(int, input().split()))
print(merge_sort(A, 0, n))

Solution (Python):
infty = 1000000000
count = 0

def merge(A, left, mid, right):
	global count
	L = A[left:mid]
	R = A[mid:right]
	L.append(infty)
	R.append(infty)
	i = 0
	j = 0
	n1 = mid - left
	for k in range(left, right):
		if L[i] <= R[j]:
			A[k] = L[i]
			i += 1
		else:
			A[k] = R[j]
			j += 1
			count += n1 - i


def mergeSort(A, left, right):
	if left + 1 < right:
		mid = (left + right) // 2
		mergeSort(A, left, mid)
		mergeSort(A, mid, right)
		merge(A, left, mid, right)


if __name__ == "__main__":
	n = int(input())
	S = list(map(int, input().split()))
	mergeSort(S, 0, n)
	print(count)

Solution (Python):



N = int(input())
A = list(map(int, input().split()))


bit = [0 for _ in range(N+1)]



def query_sum(i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i & -i
    return s



def add(i, x):
    while i <= N:
        bit[i] += x
        i += i & -i


ind_to_co = sorted(A)
co_to_ind = {}
for i, x in enumerate(ind_to_co):
    co_to_ind[x] = i+1


ans = 0
for j, a in enumerate(A):
    ind_a = co_to_ind[a]
    ans += j - query_sum(ind_a)
    add(ind_a, 1)

print(ans)

Solution (Python):

import sys
count = 0


def mearge(A, left, p, right):
    global count
    l = A[left: p]
    r = A[p: right]

    l.append(float('inf'))
    r.append(float('inf'))

    i = 0
    j = 0

    for k in range(left, right, 1):
        if l[i] <= r[j]:
            A[k] = l[i]
            i += 1
            count += j
        else:
            A[k] = r[j]
            j += 1


def mearge_sort(A, left, right):
    if left + 1 < right:
        p = (left + right) // 2
        mearge_sort(A, left, p)
        mearge_sort(A, p, right)
        mearge(A, left, p, right)


n = int(input())
A = list(map(int, sys.stdin.readline().strip().split()))
mearge_sort(A, 0, n)
print(count)

Solution (Python):
n = int(input())
A = list(map(int, input().split()))

def mergeSortInversions(arr):
    if len(arr) == 1:
        return arr, 0
    else:
        a = arr[:len(arr)//2]
        b = arr[len(arr)//2:]
        a, ai = mergeSortInversions(a)
        b, bi = mergeSortInversions(b)
        c = []
        i = 0
        j = 0
        inversions = 0 + ai + bi
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            c.append(a[i])
            i += 1
        else:
            c.append(b[j])
            j += 1
            inversions += (len(a)-i)
    c += a[i:]
    c += b[j:]
    return c, inversions

c, inversions = mergeSortInversions(A)
print(inversions)

Solution (Python):
def merge(A, c, left, mid, right):
    count = 0
    n1 = mid - left
    n2 = right - mid
    L = [0] * (n1+1)
    R = [0] * (n2+1)
    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]
    L[n1] = 2000000000
    R[n2] = 2000000000
    i = 0
    j = 0
    for k in range(left,right):
        c += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else : 
            A[k] = R[j]
            j += 1
            count += n1 - i
    return count

def mergeSort(A, c, left, right):
    if left+1 < right:
        mid = int((left + right)/2)
        c1 = mergeSort(A, c, left, mid)
        c2 = mergeSort(A, c, mid, right)
        c3 = merge(A, c, left, mid, right)
        return c1 + c2 + c3
    else :
        return 0

if __name__ == '__main__':
    n = int(input())
    A = list(map(int,input().split()))
    c = mergeSort(A, n, 0, n)
    print(str(c))

Solution (Python):

import math
n = int(input())
A = list(map(int, input().split()))
C = 0
INFTY = 1e9 + 1

def merge(S, left, mid, right):
    global C
    n1 = mid - left
    n2 = right - mid
    l = S[left:left + n1]
    r = S[mid:mid + n2]
    l.append(INFTY)
    r.append(INFTY)
    i = 0
    j = 0
    for k in range(left, right):
        if l[i] < r[j]:
            S[k] = l[i]
            i += 1
        else:
            S[k] = r[j]
            C += n1 - i
            j += 1
        

def merge_inverse(S, left, right):
    if left + 1 < right:
        mid = math.ceil((left + right) / 2)
        merge_inverse(S, left, mid)
        merge_inverse(S, mid, right)
        merge(S, left, mid, right)
merge_inverse(A, 0, n)
print(C)

Solution (Python):
SENTINEL = float('inf')


def main():
    n = int(input())
    A = list(map(int, input().split(' ')))

    result = merge_sort(A, n, 0, n)
    print(result)


def bubble_sort(array, n):
    count = 0
    for i in range(n):
        for j in range(n-1, i, -1):
            if array[j] < array[j-1]:
                count += 1
                array[j], array[j-1] = array[j-1], array[j]
    return count


def merge_sort(A, n, left, right):
    if left+1 < right:
        mid = (left+right) // 2
        v1 = merge_sort(A, n, left, mid)
        v2 = merge_sort(A, n, mid, right)
        v3 = merge(A, n, left, mid, right)
        return v1+v2+v3
    return 0


def merge(A, n, left, mid, right):
    L = A[left:mid]
    R = A[mid:right]
    L.append(SENTINEL)
    R.append(SENTINEL)
    i = j = 0
    count = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
            count += mid + j - k - 1
    return count


if __name__ == '__main__':
    main()

Solution (Python):
import sys

infty = 10**10

def merge(A,left,mid,right):

	n1 = mid -left
	n2 = right - mid

	L = [0] * n1
	R = [0] * n2

	for i in range(n1):
		L[i] = A[left+i]
	for i in range(n2):
		R[i] = A[mid+i]

	L.append(infty)
	R.append(infty)

	i = 0
	j = 0
	cnt = 0

	for k in range(left,right):


		if L[i] <= R[j]:
			A[k] = L[i]
			i = i + 1
		else:
			cnt += len(L) - 1 - i
			A[k] = R[j]
			j = j + 1
		

	return cnt

def mergeSort(A,left,right):

	cnt = 0

	if left+1 < right:

		mid = (left + right) // 2
		cnt += mergeSort(A,left,mid)
		cnt += mergeSort(A,mid,right)
		cnt += merge(A,left,mid,right)

	return cnt

def test():

	n = int(sys.stdin.readline())
	S = list(map(int,sys.stdin.readline().split()))

	result = mergeSort(S,0,n)
	
	print(result)


if __name__ == "__main__":
	test()

Solution (Python):
class MergeSort:
    def __init__(self, array):
        self._arr = array
        self._cnt = 0

    def _merge(self, left, mid, right):
        arr1 = self._arr[left:mid] + [float('inf')]
        arr2 = self._arr[mid:right] + [float('inf')]

        i, j = 0, 0
        for k in range(left, right):
            if arr1[i] <= arr2[j]:
                self._arr[k] = arr1[i]
                i += 1
            else:
                self._arr[k] = arr2[j]
                j += 1
                self._cnt += len(arr1) - i - 1


    def _merge_sort(self, left, right):
        if right <= left + 1:
            return

        mid = (left + right) // 2
        self._merge_sort(left, mid)
        self._merge_sort(mid, right)
        self._merge(left, mid, right)

    def sort(self):
        self._merge_sort(0, len(self._arr))

    def print(self):
        
        print(self._cnt)

n = int(input())
arr = [int(s) for s in input().split()]

alg = MergeSort(arr)
alg.sort()
alg.print()

Solution (Python):
def merge(A, left, mid, right):
    count = 0
    L = A[left:mid]
    R = A[mid:right]
    L.append(1000000001)
    R.append(1000000001)
    i, j = 0, 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
            if L[i] != 1000000001:
                count += mid + j - k - 1
    return count


def mergesort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        countL = mergesort(A, left, mid)
        countR = mergesort(A, mid, right)
        return merge(A, left, mid, right) + countL + countR
    return 0


def main():
    n = int(input())
    A = list(map(int, input().split()))
    ans = mergesort(A, 0, n)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def merge(A, left, mid, right):
    INF = 10**9
    global cnt
    L = A[left: mid] + [INF]
    R = A[mid: right] + [INF]
    i = 0
    j = 0
    
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
            cnt += (mid - left) - i

def mergeSort(A, left, right):
    if left+1 < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
        
n = int(input())
A = list(map(int, input().split()))
cnt = 0
mergeSort(A, 0, n)

print(cnt)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
cnt = 0
 
def marge(A, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    L = [0]*(n1+1) 
    R = [0]*(n2+1)
    
    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]
    L[n1] = pow(10,10)
    R[n2] = pow(10,10)
     
    l = 0
    r = 0
    for k in range(left, right):
        if L[l] <= R[r]:
            A[k] = L[l]
            l += 1
        else:
            A[k] = R[r]
            r += 1
            cnt += n1 - l
            
def margeSort(A, left, right):
    if 2 <= right - left:
        mid = (left + right)//2
        margeSort(A, left, mid)
        margeSort(A, mid, right)
        marge(A, left, mid, right)
     
         
margeSort(a, 0, len(a))
print(cnt)

Solution (Python):
def g(A,l,m,r):
 global c
 L,R=A[l:m]+[1e9],A[m:r]+[1e9]
 i=j=0
 for k in range(l,r):
  if L[i]<R[j]:A[k]=L[i];i+=1;c+=j
  else:A[k]=R[j];j+=1
def s(A,l,r):
 if l+1<r:m=(l+r)//2;s(A,l,m);s(A,m,r);g(A,l,m,r)
c=0
n=int(input())
A=list(map(int,input().split()))
s(A,0,n)
print(c)

Solution (Python):

SENTINEL = 2000000000

def merge(arr, length, left, mid, right):

    cnt = 0

    L = arr[left : mid]
    R = arr[mid : right]

    L.append(SENTINEL)
    R.append(SENTINEL)

    i, j = 0, 0
    for k in range(left, right):
        if (L[i] <= R[j]):
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
            cnt += len(L) - 1 - i 
    return cnt

def merge_sort(arr, length, left, right):
    if (left + 1 < right):
        mid = (left + right)//2
        v1 = merge_sort(arr, length, left, mid)
        v2 = merge_sort(arr, length, mid, right)
        v3 = merge(arr, n, left, mid, right)
        return v3 + v2 + v1
    else:
        return 0    

if __name__ == '__main__':
    n = int(input())
    A = list(map(int, input().split()))

    cnt = merge_sort(A, n, 0, n)
    print(cnt)

Solution (Python):
from typing import List


def g(elements: List[int], l: int, m: int, r: int) -> None:
    global inversion_num
    sentinel = 1000000000
    L, R = elements[l:m] + [sentinel], elements[m:r] + [sentinel]
    i = j = 0
    for k in range(l, r):
        if L[i] < R[j]:
            elements[k] = L[i]
            i += 1
            inversion_num += j
        else:
            elements[k] = R[j]
            j += 1


def s(elements: List[int], l: int, r: int) -> None:
    if l + 1 < r:
        m = (l + r) // 2
        s(elements, l, m)
        s(elements, m, r)
        g(elements, l, m, r)
    else:
        return


if __name__ == "__main__":
    n = int(input())
    elements = list(map(lambda x: int(x), input().split()))
    inversion_num = 0

    s(elements, 0, n)

    print(f"{inversion_num}")

Solution (Python):
n=int(input())
A=list(map(int,input().split()))
B=[[A[i],i+1] for i in range(n)]
B.sort()
A=[j for i,j in B]

bit=[0]*(n+1)
def add(a,w):
    x=a
    while(x<=n):
        bit[x]+=w
        x+= x&(-x)
def sum(a):
    ret=0
    x=a
    while(x>0):
        ret+=bit[x]
        x-=x&(-x)
    return ret
ans=0
for i in range(n):
    ans+=i-sum(A[i])
    add(A[i],1)
print(ans)

Solution (Python):

INF = 10**9 + 1


def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = []
    for i in range(left, mid):
        L.append(A[i])
    L.append(INF)
    R = []
    for i in range(mid, right):
        R.append(A[i])
    R.append(INF)

    i = 0
    j = 0
    k = left
    cnt = 0  
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
            cnt += n1 - i
    return cnt


def merge_sort(A, left, right):
    if right - left == 1:
        
        return 0
    mid = (left + right) / 2
    cnt1 = merge_sort(A, left, mid)  
    cnt2 = merge_sort(A, mid, right)  
    
    cnt3 = merge(A, left, mid, right)
    return cnt1 + cnt2 + cnt3


if __name__ == '__main__':
    n = int(raw_input())
    A = map(int, raw_input().split())
    print merge_sort(A, 0, n)

Solution (Python):
from enum import Enum
from queue import Queue
import collections

import sys
import math

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

def bubbleSort(A):
    count = 0
    for i in range(1,len(A)):
        for j in range(1,len(A)-i+1):
            if A[j] < A[j-1]:
                A[j],A[j-1] = A[j-1],A[j]
                count += 1
    return A,count

def merge(A, left, mid, right):
    count = 0

    L = A[left:mid] + [BIG_NUM]
    R = A[mid:right] + [BIG_NUM]
    i = 0
    j = 0
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
            count += len(L)-1-i
    return count

def mergeSort(A, left, right):
    if left+1 < right:
        mid = (left + right)//2
        cnt1 = mergeSort(A, left, mid)
        cnt2 = mergeSort(A, mid, right)
        cnt3 = merge(A, left, mid, right)
        return cnt1+cnt2+cnt3
    else:
        return 0

n = int(input())
A = list(map(int,input().split()))
cnt=0
cnt = mergeSort(A,0,n)

print(cnt)

Solution (Python):
def g(A,l,m,r):
 global c
 L,R=A[l:m]+[1e9],A[m:r]+[1e9]
 i=j=0
 for k in range(l,r):
  if L[i]<R[j]:A[k]=L[i];i+=1;c+=j
  else:A[k]=R[j];j+=1
def s(A,l,r):
 if l+1<r:m=(l+r)//2;s(A,l,m);s(A,m,r);g(A,l,m,r)
c=0
n=int(input())
A=list(map(int,input().split()))
s(A,0,n)
print(c)

Solution (Python):
count = 0

def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L, R = A[left: left + n1], A[mid: mid + n2]
    global count

    L.append(2000000000)
    R.append(2000000000)

    i, j = 0, 0
    for k in range(left, right):
        
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            count += len(L) - 1 - i
            j += 1


def mergeSort(A, left, right):
    
    if left + 1 < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)


n = int(input())
input_list = list(map(int, input().split(' ')))

mergeSort(input_list, 0, n)
print(count)

Solution (Python):
n = int(input())
A = list(map(int,input().split()))

def g(A,l,m,r):
  global c
  L,R = A[l:m]+[1e11],A[m:r]+[1e11]
  i = j = 0
  for k in range(l,r):
    if L[i] < R[j]:
      A[k] = L[i]
      i += 1
      c += j
    else:
      A[k] = R[j]
      j += 1

def s(A,l,r):
  if l + 1 < r:
    m = (l+r)//2
    s(A,l,m)
    s(A,m,r)
    g(A,l,m,r)

c = 0

s(A,0,n)
print(c)

Solution (Python):
INFTY = 1000000001

def merge(A, left, mid, right):
    global cnt

    L = A[left:mid]
    R = A[mid:right]

    L.append(INFTY)
    R.append(INFTY)

    i = 0
    j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
          A[k] = L[i]
          i += 1
        else:
          A[k] = R[j]
          j += 1
          cnt += ((mid - left) - i)



def merge_sort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2

        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)



n = int(input())
S = list(map(int, input().split()))

cnt = 0

merge_sort(S, 0, n)


print(cnt)

Solution (Python):
def inversion(l,r):
    if l == r:
        return [lis[l]],0
    if l+1 == r:
        L=lis[l]
        R=lis[r]
        if L < R:
            return [L,R],0
        else:
            return [R,L],1
    else:
        m = (l+r)//2
        lis1,c1 = inversion(l,m)
        lis2,c2 = inversion(m+1,r)
        reslis,cres = merge(lis1,lis2)
        return reslis,c1+c2+cres

def merge(lis1,lis2):
    len1=len(lis1)
    len2=len(lis2)
    i = 0
    j = 0
    reslis = []
    count = 0
    for _ in range(len1+len2+1):
        if i==len1 or j==len2:
            if i==len1:
                reslis = reslis + lis2[j:]
            elif j==len2:
                reslis = reslis + lis1[i:]
            break
        else:
            if lis1[i] < lis2[j]:
                reslis.append(lis1[i])
                i += 1
            elif lis1[i] > lis2[j]:
                reslis.append(lis2[j])
                j += 1
                count += len1-i
    return reslis,count

n = int(input())
lis = list(map(int,input().split()))
reslis,count = inversion(0,len(lis)-1)
print(count)

Solution (Python):
n = int(input())
A = [int(i) for i in input().split()]

def merge(A, left, mid, right, cnt):
    L = A[left:mid]
    R = A[mid:right]
    i = 0
    j = 0
    L.append(1000000000)
    R.append(1000000000)
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            if k < mid + j:
                cnt += mid + j - k
            A[k] = R[j]
            j += 1
    return A, cnt

def mergeSort(A, left, right, cnt):
    if left+1 < right:
        mid = (left + right)//2
        A, cnt = mergeSort(A, left, mid, cnt)
        A, cnt = mergeSort(A, mid, right, cnt)
        A, cnt = merge(A, left, mid, right, cnt)
    return A, cnt

A, cnt = mergeSort(A, 0, n, 0)
print(cnt)

Solution (Python):
c=0
import sys
def merge(x, y):
  i=j=0
  res = []
  while j<len(y) or i<len(x):    
    while i<len(x) and (j>=len(y) or x[i]<=y[j]):

      res.append(x[i])
      i+=1
    if j<len(y):
      global c
      res.append(y[j])
      c+=len(x)-i
    j+=1
  return res
  
def sort(x):
  if len(x)>1:
    l = sort(x[:len(x)//2])
    r = sort(x[len(x)//2:])
    merged=merge(l, r)
    return merged
  else:
    return x
input()
a=list(map(int, input().split()))
sort(a)

print(c)

Solution (Python):
def merge(a):
    if len(a) == 1:
        return a, 0
    mid = len(a) // 2
    al, cnt_l, ar, cnt_r = *merge(a[:mid]), *merge(a[mid:])
    res_cnt, res_arr = 0, []
    while 0 < len(al) and 0 < len(ar):
        if al[-1] <= ar[-1]:
            res_arr.append(al.pop())
        else:
            res_arr.append(ar.pop())
            res_cnt += len(al)
    res_arr.reverse()
    return ar + al + res_arr, res_cnt + cnt_l + cnt_r


def inversion_count(a):
    return merge(a)[1]


def main():
    input()
    a = list(map(int, input().split()))
    print(inversion_count(a))


if __name__ == '__main__':
    main()

Solution (Python):
class BinaryIndexedTree(object):
    __slots__ = ["tree", "size"]

    def __init__(self, size: int):
        self.tree = [0]*(size+1)
        self.size = size+1

    def add(self, index: int, value: int):
        tree = self.tree

        while index < len(tree):
            tree[index] += value
            index += index & -index

    def sum(self, index: int):
        tree, result = self.tree, 0

        while index:
            result += tree[index]
            index -= index & -index

        return result


def solve(A):
    bit = BinaryIndexedTree(len(A)+1)
    ans = 0
    for i, n in enumerate(A):
        ans += i - bit.sum(n-1)
        bit.add(n, 1)

    return ans


if __name__ == "__main__":
    input()
    a = list(map(int, input().split()))
    d = {n: i for i, n in enumerate(sorted(a), start=1)}
    a = [d[n] for n in a]
    print(solve(a))

Solution (Python):
import math
c = 0
l = [0] * 500000
r = [0] * 500000


def merge(a, left, mid, right):
    global c
    n1 = mid - left
    n2 = right - mid
    for i in range(n1):
        l[i] = a[left + i]
    for i in range(n2):
        r[i] = a[mid + i]
    l[n1] = math.inf
    r[n2] = math.inf
    i, j = 0, 0
    cnt = 0
    for k in range(left, right):
        c += 1
        if l[i] <= r[j]:
            a[k] = l[i]
            i += 1
        else:
            a[k] = r[j]
            j += 1
            cnt += n1 - i
    return cnt


def mergeSort(a, left, right):
    cnt = 0
    if (left + 1) < right:
        mid = (left + right) // 2
        cnt += mergeSort(a, left, mid)
        cnt += mergeSort(a, mid, right)
        cnt += merge(a, left, mid, right)
    return cnt


n = int(input())
*s, = map(int, input().split())

print(mergeSort(s, 0, n))

Solution (Python):





class Bit:
    def __init__(self, num):
        self.size = num
        self.tree = [0] * (num + 1)
  
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
  
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

n = int(input().rstrip())
A = list(map(int,input().rstrip().split()))

A = [i+1 for i in sorted(range(len(A)), key=A.__getitem__)]
bit = Bit(n)

ans = 0
for i,ai in enumerate(A[::-1]):
    ans += bit.sum(ai)
    bit.add(ai, 1)
 
print(ans)

Solution (Python):
import bisect


def sum(i):
    s = 0
    while(i > 0):
        s += bit[i]
        i = i&(i-1)
    return s

def add(i,x):
    while(i <= n):
        bit[i] += x
        i += i & (-i)

n = int(input())
a = list(map(int,input().split()))
aa = sorted(a)

bit = [0]

for i in range(n):
    a[i] = bisect.bisect_left(aa,a[i])+1
    bit.append(0)

ans = 0

for i in range(n):
    ans += (i - sum(a[i]))
    add(a[i],1)

print(ans)