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):
from sys import stdin


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

    def sum(self, i):
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & (-i)

        return res

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & (-i)


def inversion_num(A):
    count = 0
    bit = BIT(max(A))
    for j in range(len(A)):
        count += j-bit.sum(A[j])
        bit.add(A[j], 1)

    return count

n = int(stdin.readline().rstrip())
a = [int(x) for x in stdin.readline().rstrip().split()]
dic = {}
for i, a_i in enumerate(sorted(a), 1):
    dic[a_i] = i


a = [dic[a_i] for a_i in a]
print(inversion_num(a))

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

def merge(lst,left,middle,right):
    cnt = 0 

    left_lst  = lst[left:middle]+[INF]
    right_lst = lst[middle:right]+[INF]

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

def merge_sort(lst,left,right):
    while left+1 < right:
        middle = (left+right)//2
        left_cnt  = merge_sort(lst,left,middle)
        right_cnt = merge_sort(lst,middle,right)
        return merge(lst,left,middle,right)+left_cnt+right_cnt
    return 0

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

Solution (Python):
import sys
from typing import List
import math

n = int(input())
S = [int(i) for i in input().split()]


def merge(A: List[int], left: int, mid: int, right: int) -> None:
    global cnt

    left_list = A[left:mid]
    right_list = A[mid:right]
    n_left = len(left_list)
    left_list.append(sys.maxsize)
    right_list.append(sys.maxsize)

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


def merge_sort(A: List[int], left: int, right: int) -> int:
    if left + 1 < right:
        mid = math.floor((left + right) / 2)
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)


hikaku = 0
cnt = 0
merge_sort(S, 0, len(S))
print(cnt)

Solution (Python):
def swap(list,i,j,count):
    if(list[j]<list[i]):
        list[i],list[j]=list[j],list[i]
        count[0]+=1
        return 1
    return 0

def merge(list,left1,left2,right2,count):
    i=left1
    j=left2
    tmp_list=[]
    while(1):
        if(list[i] <=list[j]):
            tmp_list.append(list[i])
            i+=1
        else:
            tmp_list.append(list[j])
            j+=1
            count[0]+=left2-i
        if(i==left2):
            for k in range(j,right2):
                tmp_list.append(list[k])
            break
        if(j==right2):
            for k in range(i,left2):
                tmp_list.append(list[k])
            break
    for k in range(left1,right2):
        list[k]=tmp_list[k-left1]
    

                
                
    
        



def merge_sort(list,left,right,count):
    if(right  == left ):
        return None
    if(left+1 == right):
        swap(list,left,right,count)
    else:
        mid=(left + right)//2
        merge_sort(list,left,mid,count)
        merge_sort(list,mid+1,right,count)
        merge(list,left,mid+1,right+1,count)
        

n=int(input())
data=list(map(int,input().split()))
count=[0]
merge_sort(data,0,n-1,count)
print(count[0])

Solution (Python):
import sys
readline = sys.stdin.readline
write = sys.stdout.write

N = int(readline())
*A, = map(int, readline().split())

data = [0]*(N+1)
def add(k, v):
    while k <= N:
        data[k] += v
        k += k & -k
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s


ans = N*(N-1)//2
for a in map({a: i+1 for i, a in enumerate(sorted(A))}.__getitem__, A):
    ans -= get(a)
    add(a, 1)
write("%d\n" % ans)

Solution (Python):
import sys

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

nchg=0
def merge(left, mid, right):
    global a, nchg
    i=0
    j=0
    ll = a[left:mid+1]
    rr = a[mid+1:right+1]
    n1 = mid-left+1
    n2 = right-mid
    while i<n1 or j<n2:
        if i==n1:
            a[left+i+j] = rr[j]
            j += 1
            nchg += n1-i
            continue
        if j==n2:
            a[left+i+j] = ll[i]
            i += 1
            continue
        if ll[i] <= rr[j]:
            a[left+i+j] = ll[i]
            i += 1
        else:
            a[left+i+j] = rr[j]
            nchg += n1-i
            j += 1


def mergesort(left, right):
    if right-left>0:
        mid=(left+right)//2
        mergesort(left, mid)
        mergesort(mid+1, right)
        merge(left, mid, right)


mergesort(0, n-1)
print(nchg)

Solution (Python):

"""
Created on Sun Sep 30 17:27:26 2018
KyotoE
@author: maezawa
"""

n = int(input())
parray = list(map(int, input().split()))
larray = [0]*n
rarray = [0]*n


def merge(a, n, left, mid, right):
    cnt = 0
    n1 = mid - left
    n2 = right -mid
    for i in range(n1):
        larray[i] = a[left+i]
    for i in range(n2):
        rarray[i] = a[mid+i]
    larray[n1] = 10**10
    rarray[n2] = 10**10
    i = 0
    j = 0
    for k in range(left,right):
        if larray[i] <= rarray[j]:
            a[k] = larray[i]
            i += 1
        else:
            a[k] =rarray[j]
            j += 1
            cnt += n1 - i
    return cnt

def mergesort(a, n, left, right):
    if left+1 < right:
        mid = (left+right)//2
        v1 = mergesort(a, n, left, mid)
        v2 = mergesort(a, n, mid, right)
        v3 = merge(a, n, left, mid, right)
        return v1+v2+v3
    else:
        return 0
    
ans = mergesort(parray, n, 0, n)
print(ans)

Solution (Python):
from array import array
import bisect
import collections
import heapq
import itertools
import operator
import sys


class BIT:
    def __init__(self, n):
        self.n = n
        self.arr = array("l", [0] * (n + 1))

    def __str__(self):
        return str(self.arr.tolist())

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

    def sum(self, i, j=None):
        if j is None:
            s = 0
            while i > 0:
                s += self.arr[i]
                i -= i & -i
            return s

        if i > j:
            raise ValueError

        return self.sum(j) - self.sum(i - 1)


def main():
    n = int(sys.stdin.readline())
    nums = list(map(int, sys.stdin.readline().split()))
    d = dict((num, i) for i, num in enumerate(sorted(set(nums)), 1))
    
    bit = BIT(n + 1)

    ans = 0
    for num in nums:
        bit.add(d[num], 1)
        
        ans += bit.sum(d[num] + 1, n + 1)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import math
c = 0

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

def marge(A, right, mid, left):
    global c
    L, R = A[right:mid], A[mid:left]
    R.append(int(10E10))
    L.append(int(10E10))
    i, j = 0, 0
    smin = int(10E10)
    nums = 0
    for k in range(right, left):
        if L[i] <= R[j]:
            if smin < L[i]:
                c = c + (len(L) - i - 1) * nums
                
                
                smin,nums = int(10E10), 0
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            smin, nums = R[j], nums + 1
            j = j + 1

def marge_sort(A, right, left):
    if right + 1 < left:
        mid = math.ceil((left + right) / 2)
        marge_sort(A, right, mid)
        marge_sort(A, mid, left)
        marge(A, right, mid, left)

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

Solution (Python):
n = int(input())
nlist = list(map(int, input().split()))
W = [0for i in range(n)]
def M(l,r):      
    if (l+1 >= r):
        return 0
    elif (l+2 == r):
        if (nlist[l] <= nlist[l+1]):
            return 0
        else:
            nlist[l],nlist[l+1] = nlist[l+1],nlist[l]
            return 1
    
    m = (l+r)//2
    i = l
    j = m
    k = l
    cl = M(l,m)
    cr = M(m,r)
    c = 0
    while (i<m and j<r):
        if (nlist[i] <= nlist[j]):
            W[k] = nlist[i] 
            k += 1
            i += 1
        else:
            W[k] = nlist[j]  
            k += 1
            j += 1
            c += (m-i)  
                        
    while (i<m):   
        W[k] = nlist[i]
        k += 1
        i += 1
    while (j<r):   
        W[k] = nlist[j]
        k += 1
        j += 1
    for i in range(l,r): 
        nlist[i] = W[i]
    return cl+cr+c
        
print(M(0,n))

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

def merge(A, left, mid, right):
    num = 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] = float("inf")
    R[n2] = float("inf")
    i = 0
    j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            num += n1 - i
            A[k] = R[j]
            j += 1
    return num
            
def merge_sort(A, left, right):
    if not(left + 1 < right):
        num = 0
    else:
        mid = (left + right)//2
        num_left = merge_sort(A, left, mid)
        num_right = merge_sort(A, mid, right)
        num_merge = merge(A, left, mid, right)
        num = num_left + num_right + num_merge
    return num

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

Solution (Python):
def number_of_inv(A, n):
    cnt = 0

    def merge(A, left, mid, right):
        L = A[left:mid]
        R = A[mid:right]
        n = right - left
        n1 = mid - left
        C = [0] * n
        L.append(float('inf'))
        R.append(float('inf'))
        i = 0
        j = 0
        nonlocal cnt
        for k in range(left, right):
            if L[i] <= R[j]:
                A[k] = L[i]
                i += 1
            else:
                A[k] = R[j]
                cnt += n1 - i
                j += 1
        return cnt

    def merge_sort(A, left, right):
        if left+1 < right:
            mid = (left + right) >> 1
            merge_sort(A, left, mid)
            merge_sort(A, mid, right)
            return merge(A, left, mid, right)
    
    if len(A) == 1:
        return 0
    else:
        return merge_sort(A, 0, n)

n = int(input())
A = [int(i) for i in input().split()]
print(number_of_inv(A, n))

Solution (Python):
def merge(a, left, mid, right):
    cnt = 0
    n1 = mid - left
    n2 = right - mid
    l = a[left:left+n1]
    r = a[mid:mid+n2]
    l.append(float('inf'))
    r.append(float('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 += n1 - i
    return cnt


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


n = int(input())
a = [int(v) for v in input().split()]

ans = mergeSort(a, 0, n)
print(ans)

Solution (Python):

def conq(A,left,mid,right):
    global c
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid] + [10**9+1]
    R = A[mid:right] + [10**9+1]
    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
            c += n1 - i

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

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