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 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)
if'__main__'==__name__:
 c=0
 n=int(input())
 A=list(map(int,input().split()))
 s(A,0,n)
 print(c)

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)
if'__main__'==__name__:
 c=0
 n=int(input())
 A=list(map(int,input().split()))
 s(A,0,n)
 print(c)

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)
def m():
 n,A=int(input()),list(map(int,input().split()))
 s(A,0,n);print(c)
if'__main__'==__name__:c=0;m()

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)
def m():
 n,A=int(input()),list(map(int,input().split()))
 s(A,0,n);print(c)
if'__main__'==__name__:c=0;m()

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)
def m():
 n,A=int(input()),list(map(int,input().split()))
 s(A,0,n);print(c)
if'__main__'==__name__:c=0;m()

Solution (Python):

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

            cnt += n1 - i
            A[k] = R[j]
            j += 1

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)

input()
a = list(map(int, input().split()))
merge_sort(a, 0, len(a))
print(cnt)

Solution (Python):
def count(nums):
    """count the number of inversions (ai > aj and i < j)
    in a sequence of ints num.

    >>> count([3, 5, 2, 1, 4])
    6
    >>> count([10, 2, 9, 4, 6, 5, 7, 8, 3, 1])
    29
    """
    def _count(i, j):
        if i < j:
            mid = (i + j) // 2
            i1, li1 = _count(i, mid)
            i2, li2 = _count(mid+1, j)

            return _merge(li1, li2, i1 + i2)
        else:
            return (0, nums[i:i+1])

    def _merge(li1, li2, invs):
        i = j = 0
        result = []
        sums = inv = 0
        while i < len(li1) and j < len(li2):
            if li1[i] > li2[j]:
                result.append(li2[j])
                inv += 1
                j += 1
            else:
                result.append(li1[i])
                invs += sums + inv
                sums += inv
                inv = 0
                i += 1

        while i < len(li1):
            result.append(li1[i])
            invs += sums + inv
            sums += inv
            inv = 0
            i += 1
        if j < len(li2):
            result.extend(li2[j:])

        return (invs, result)

    invs, _ = _count(0, len(nums))
    return invs

def run():
    _ = int(input())  
    nums = [int(i) for i in input().split()]

    print(count(nums))


if __name__ == '__main__':
    run()

Solution (Python):
import math
def merge(a, left, mid, right):
    global c
    n1 = mid - left
    n2 = right - mid
    l = a[left:left + n1]
    r = a[mid:mid + n2]
    l.append(10e10)
    r.append(10e10)
    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]
            c += n1 - i
            j += 1

def mergeSort(a, left, right):
    if left + 1 < right:
        mid = math.ceil((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()))
c = 0
mergeSort(a, 0, n)
print(c)

Solution (Python):
n = int(input())
lis = list(map(int,input().split()))
def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    
    left = arr[:mid]
    right = arr[mid:]

    
    left = merge_sort(left)
    right = merge_sort(right)

    
    return merge(left, right)


def merge(left, right):
    global ans
    merged = []
    l_i, r_i = 0, 0

    
    while l_i < len(left) and r_i < len(right):
        
        if left[l_i] <= right[r_i]:
            merged.append(left[l_i])
            l_i += 1
        else:
            merged.append(right[r_i])
            r_i += 1
            ans += (len(left) - l_i)

    
    if l_i < len(left):
        merged.extend(left[l_i:])
    if r_i < len(right):
        merged.extend(right[r_i:])
    return merged

ans = 0
merge_sort(lis)
print(ans)

Solution (Python):




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











def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    left = merge_sort(left)
    right = merge_sort(right)

    return merge(left, right)


def merge(left, right):
    global ans
    merged = []
    l_i, r_i = 0, 0

    while l_i < len(left) and r_i < len(right):
        if left[l_i] <= right[r_i]:
            merged.append(left[l_i])
            l_i += 1
        else:
            merged.append(right[r_i])
            r_i += 1
            ans += (len(left) - l_i)

    if l_i < len(left):
        merged.extend(left[l_i:])
    if r_i < len(right):
        merged.extend(right[r_i:])
    return merged

ans = 0
merge_sort(lis)
print(ans)

Solution (Python):

count=0
def merge(A, left, mid, right):
    global count
    h=[]
    L=A[left:mid]+[2**32]
    R=A[mid:right]+[2**32]
    i=0
    j=0
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k] = L[i]
            h.append(L[i])
            i += 1
        else:
            A[k] = R[j]
            h.append(R[j])
            j += 1
            if i < len(L)-1:
                count += len(L) - 1 - 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)

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

Solution (Python):
count=0
def merge(A, left, mid, right):
    global count
    h=[]
    L=A[left:mid]+[2**32]
    R=A[mid:right]+[2**32]
    i=0
    j=0
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k] = L[i]
            h.append(L[i])
            i += 1
        else:
            A[k] = R[j]
            h.append(R[j])
            j += 1
            if i < len(L)-1:
                count += len(L) - 1 - 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)

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

Solution (Python):



global cnt
cnt=0

def merge(A,left,mid,right):
    L=A[left:mid]
    R=A[mid:right]
    L.append(float("inf"))
    R.append(float("inf"))
    
    i=0
    j=0
    for k in range(left,right):
        global cnt
        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=(int)((left+right)/2)
        mergeSort(A,left,mid)
        mergeSort(A,mid,right)
        merge(A,left,mid,right)

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

mergeSort(S,0,n)
print(cnt)

Solution (Python):
global cnt
cnt=0

def merge(A,left,mid,right):
    L=A[left:mid]
    R=A[mid:right]
    L.append(float("inf"))
    R.append(float("inf"))
    
    i=0
    j=0
    for k in range(left,right):
        global cnt
        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=(int)((left+right)/2)
        mergeSort(A,left,mid)
        mergeSort(A,mid,right)
        merge(A,left,mid,right)

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

mergeSort(S,0,n)
print(cnt)

Solution (Python):
def merge(A, left, mid, right):
    count = 0
    L = A[left: mid]
    R = A[mid: right]
    L.append(10e9 + 1)
    R.append(10e9 + 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
            count += (len(L)-1) - i
    return count

def merge_sort(A, left, right):
    if left + 1 < right:
        mid = int((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
    else:
        return 0

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

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

Solution (Python):
n = int(input())
s = list(map(int, input().split()))
cnt = 0
SENTINEL = 10e9 + 1
def merge(a, left, mid, right):
    global cnt
    l = a[left: mid] + [SENTINEL]
    r = a[mid: right] + [SENTINEL]
    n1 = mid - left
    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]
            cnt += n1 - i
            j += 1

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)

merge_sort(s, 0, n)
print(cnt)

Solution (Python):
global cnt
cnt = 0

def merge(A, left, mid, right):
    L = A[left:mid] + [float("inf")]
    R = A[mid:right] + [float("inf")]

    i = 0
    j = 0
    global cnt
    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] != float("inf"):
                cnt += len(L)-1-i

def mergesort(A, left, right):
    rsl = []
    if left+1 < right:
        mid = int((left+right)/2)
        mergesort(A, left, mid)
        mergesort(A, mid, right)
        rsl = merge(A, left, mid, right)

    return rsl


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

mergesort(S, 0, n)
print(cnt)

Solution (Python):

def merge(a, left, mid, right):
    x = 0
    l = a[left:mid] + [float("inf")]
    r = a[mid:right] + [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
            x += mid - (left+i)
    return x

def mergeSort(a, left, right,x):
    if left+1 < right:
        mid = int((left + right)/2)
        mergeSort(a, left, mid,x)
        mergeSort(a, mid, right,x)
        x[0] += merge(a, left, mid, right)

n = int(input())
s = list(map(int,input().split()))
x = [0]
mergeSort(s,0,n,x)
print(x[0])

Solution (Python):
import math
def merge(a, left, mid, right):
    global c
    n1 = mid - left
    n2 = right - mid
    l = a[left:left + n1]
    r = a[mid:mid + n2]
    l.append(10e10)
    r.append(10e10)
    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]
            c += n1 - i
            j += 1
 
def mergeSort(a, left, right):
    if left + 1 < right:
        mid = math.ceil((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()))
c = 0
mergeSort(a, 0, n)
print(c)

Solution (Python):
n = int(input())
s = list(map(int,input().split()))
count = 0
 
def merge(a, left, mid, right):
    global count
    l = a[left:mid] + [float("inf")]
    r = a[mid:right] + [float("inf")]
    i = 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) - i - 1
def mergeSort(a, left, right):
    if left + 1 < right:
        mid = right + (left - right)//2
        mergeSort(a, left, mid)
        mergeSort(a, mid, right)
        merge(a, left, mid, right)
 
mergeSort(s, 0, n) 
print(count)

Solution (Python):
INF = 10**10


def merge(ary, left, mid, right):
    lry = ary[left:mid]
    rry = ary[mid:right]
    lry.append(INF)
    rry.append(INF)

    cnt = 0
    i = 0
    j = 0
    for k in range(left, right):
        if lry[i] <= rry[j]:
            ary[k] = lry[i]
            i += 1
        else:
            ary[k] = rry[j]
            j += 1
            cnt += len(lry) - 1 - i

    return cnt


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

    return cnt


if __name__ == '__main__':
    n = int(input())
    ary = [int(_) for _ in input().split()]
    print(merge_sort(ary, 0, n))

Solution (Python):
cnt = 0
def merge(A,left,mid,right):
    global cnt
    n1 = mid - left
    n2 = right - mid

    L = [A[i] for i in range(left, mid)]
    R = [A[i] for i in range(mid, right)]
    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:
            cnt += n1 - i
            A[k] = R[j]
            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)

input()
a = list(map(int, input().split()))
mergeSort(a, 0, len(a))
print(cnt)

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):
def merge(a, left, mid, right):
    INF = int(1e+11)
    l = a[left:mid]
    r = a[mid:right]
    l.append(INF)
    r.append(INF)
    i = 0
    j = 0

    ans = 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] != INF:
                ans += mid - left - i

    return ans


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

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

print(merge_sort(a, 0, len(a)))

Solution (Python):






from collections import defaultdict
import sys
input = sys.stdin.readline


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

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

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


def solve(n, A):
    ans = 0
    bit = FenwickTree(n)
    B = sorted(A)

    d = defaultdict(int)
    for i in range(n):
        d[B[i]] = i

    for i in range(n):
        t = A[i]
        ind = d[t] + 1
        ans += i - bit.sum(ind)
        bit.add(ind, 1)

    return ans


def main():
    n = int(input().strip())
    A = [int(i) for i in input().strip().split()]

    ans = solve(n, A)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline

n = int(input())
A = [int(x) for x in input().split()]
cnt = 0

def Merge(S, l, m, r):
    global cnt
    L = S[l:m] + [float('inf')]
    R = S[m:r] + [float('inf')]
    i, j = 0, 0
    for k in range(l, r):
        if L[i] < R[j]:
            S[k] = L[i]
            i += 1
        else:
            S[k] = R[j]
            cnt += len(L) - 1 - i
            j += 1
    return

def MergeSort(S, l, r):
    if r - l > 1:
        m = (l + r) // 2
        MergeSort(S, l, m)
        MergeSort(S, m, r)
        Merge(S, l, m, r)
    return

MergeSort(A, 0, n)
print(cnt)

Solution (Python):

from collections import defaultdict
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0]*(n+1)
    self.el = [0]*(n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i-1)

def solve():
  ans = 0
  N = int(input())
  bit = BIT(N)
  A = list(map(int, input().split()))
  dic = {a:i+1 for i,a in enumerate(sorted(A))}
  for i in range(N):
    A[i] = dic[A[i]]
  for i in range(N):
    ans += i - bit.sum(A[i])
    bit.add(A[i],1)
  return ans
print(solve())

Solution (Python):
n = int(input())
S = [*map(int, input().split())]
t = [0]

def merge(A, left, mid, right):
  L = A[left:mid] + [float("inf")]
  R = A[mid:right] + [float("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]
      t[0] += mid + j - k
      j += 1
  return right - left

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

count = merge_sort(S, 0, n)
print(t[0])

Solution (Python):
count = 0



def merge(list1, list2):
    global count
    output = []
    p1 = 0
    p2 = 0
    l1 = len(list1)
    l2 = len(list2)
    while p1<l1 and p2<l2:
        num1 = list1[p1]
        num2 = list2[p2]
        if num1 <= num2:
            output.append(num1)
            p1 += 1
        else:
            output.append(num2)
            p2 += 1
            count += l1 - p1
    return output+list1[p1:]+list2[p2:]



def counting_merge_sort(list1):
    if len(list1) <= 1:
        return list1
    pivot = len(list1)//2
    return merge(counting_merge_sort(list1[:pivot]), counting_merge_sort(list1[pivot:]))

n = int(input())
list1 = list(map(int, input().split(' ')))
counting_merge_sort(list1)
print(count)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    n = NI()
    A = LI()
    S = sorted(A)

    bit = [0] * (n+1)

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

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

    ans = 0
    for i,x in enumerate(A):
        z = bisect.bisect_left(S,x) + 1
        bit_add(z,1)
        ans += z - bit_sum(z)
    print (ans)

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
A = [int(x) for x in list(input().split())]
B = [[A[i], i + 1] for i in range(n)]
B.sort()
A = [j for i, j in B]
bit = [0] * (n + 2)
ans = 0
for i in range(n):
    ret = 0
    a = A[i]
    while 0 < a:
        ret += bit[a]
        a -= a & (-a)
    ans += i - ret
    a = A[i]
    while a <= n:
        bit[a] += 1
        a += a & (-a)
print(ans)

Solution (Python):
def merge(a,left,mid,right):
    count=0
    L=a[left:mid]+[float("inf")]
    R=a[mid:right]+[float("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+=mid-left-i
    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)
        countm=merge(a,left,mid,right)
        return countm+countl+countr
    return 0



n=int(input())
a=[int(i)for i in input().split()]
ans=mergeSort(a,0,n)
print(ans)

Solution (Python):
num = int(input())
arr = list(map(int, input().split()))

num_of_inversions = 0

def merge(arr, left, middle, right, count):
    global num_of_inversions

    L = arr[left:middle]
    L.append(float('inf'))
    R = arr[middle:right]
    R.append(float('inf'))

    offset = len(L) - 1 + left
    countL, countR = 0, 0

    iterL, iterR = iter(L), iter(R)
    l,r = next(iterL), next(iterR)

    for index in range(left, right):
        count += 1
        if l <= r:
            arr[index] = l
            l = next(iterL)
            countL += 1
        else:
            arr[index] = r
            r = next(iterR)
            num_of_inversions += countR - index + offset
            countR += 1
    return count

def merge_sort(arr, left, right, count):
    if left + 1 < right:
        pivot = (left + right) // 2
        count = merge_sort(arr, left,  pivot, count)
        count = merge_sort(arr, pivot, right, count)

        count = merge(arr, left, pivot, right, count)
    return count

_ = merge_sort(arr, 0, num, 0)
print(num_of_inversions)

Solution (Python):
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array





sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L, R = [0] * (n1 + 1), [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, j = 0, 0
    reverse_cnt = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            reverse_cnt += n1 - i
            A[k] = R[j]
            j += 1
    return reverse_cnt


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


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    q = merge_sort(A, 0, N)
    print(q)


if __name__ == '__main__':
    main()

Solution (Python):
def invr(x):
    if len(x)<=1:
        return x,0
    m=len(x)
    x1=x[:m//2]
    x2=x[m//2:]
    x11,r1=invr(x1)
    x22,r2=invr(x2)
    x11=x11[::-1]
    x22=x22[::-1]
    rx=[];r=r1+r2
    while x11 and x22:
        if x11[-1]<=x22[-1]:
            rx.append(x11.pop())
        else:
            rx.append(x22.pop())
            r+=len(x11)
    rx+=x11[::-1]
    rx+=x22[::-1]
    return rx,r
n=int(input())
*a,=map(int, input().split())
_,ans=invr(a)
print(ans)

Solution (Python):
from math import inf


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

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

    L.append(inf)
    R.append(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
            count += mid - left - i


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


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

    merge_sort(A, 0, n)
    print(count)


if __name__ == "__main__":
    count = 0
    main()

Solution (Python):


import bisect

n = int(input())
a = list(map(int,input().split()))
b = [0]*n
c = sorted(a)

for i in range(n):
    d = bisect.bisect(c,a[i])
    b[i] = d

data = [0] * (n+1)

def init(k,x):
    while k <= n:
        data[k] += x
        k += k & -k
        
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
    
ans = 0
for i in range(n-1,-1,-1):
    init(b[i],1)
    ans += get(b[i]-1)

print(ans)

Solution (Python):
import math

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

cnt = 0

def merge(A, left, mid, right):
    global cnt
    L, R = [], []
    for a in A[left:mid]:
        L.append(a)
    for a in A[mid:right]:
        R.append(a)
    L.append(math.inf)
    R.append(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
            cnt += len(L) - 1 - i
            
            
def mergeSort(A, left, right):
    if right - left > 1:
        mid = (right + left) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
mergeSort(A, 0, len(A))
print(cnt)

Solution (Python):

import sys
sys.setrecursionlimit(10**7)
input= lambda:sys.stdin.readline().rstrip()
N=int(input())
class BIT:
    
    def __init__(self,n):
        self.n=n
        self.data=[0]*(n+1)
    def to_sum(self,i):
        
        s=0     
        while i>0:
            s+=self.data[i]
            i-=(i& -i)
        return s
    def add(self,i,x):
        
        while i<=self.n:
            self.data[i]+=x
            i+=(i & -i)
    def get(self,i,j):
        
        return self.to_sum(j)-self.to_sum(i-1)
ans = 0

A=list(map(int,input().split()))
B=sorted(A)
how_big={B[i]:i+1 for i in range(N)}
tree = BIT(N+100)

for index, p in enumerate(A):
    tree.add(how_big[p], 1)
    
    ans += index+1-tree.to_sum(how_big[p])
print(ans)

Solution (Python):
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 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


def main():
    N = int(input())
    *A, = map(int, input().split())

    compress_dict = {x: i for i, x in enumerate(sorted(set(A)), start=1)}
    M = len(compress_dict)

    bit = Bit(M)
    ans = 0
    for cnt, x in enumerate(A, start=1):
        x = compress_dict[x]
        bit.add(x, 1)
        ans += cnt - bit.sum(x)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

N_MAX = 200000 + 5
INF = 10**9
sys.setrecursionlimit(N_MAX)
MOD = 10**9 + 7

N = int(sys.stdin.readline())
A = [int(x) for x in sys.stdin.readline().split()]

z = 0
c = 0

def merge(A, left, right):

    global c, z

    n1 = (right - left) // 2 + left  

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

    L.append(INF)
    R.append(INF)

    

    i = 0
    j = 0
    l = len(L)
    for k in range(left, right):
        z += 1

        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
            
            c += l-i-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, right)


mergesort(A, 0, N)



print(c)

Solution (Python):
class BIT:
    ''' binary indexed tree '''
    def __init__(self, size):
        self.size = size
        self.bit = [0] * (size + 1) 
    def add(self, pos, x):
        ''' bit の pos の位置に x を加える '''
        while pos <= self.size:
            self.bit[pos] += x
            pos += self.right_most_bit(pos)
    def sum(self, pos):
        ''' bit の 1...pos の和を返す '''
        ans = 0
        while pos > 0:
            ans += self.bit[pos]
            pos -= self.right_most_bit(pos)
        return ans
    def right_most_bit(self, x):
        return x & -x

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


aa = sorted(a)
d = {k:v for v, k in enumerate(aa)}
b = BIT(n)

cnt = 0
index = 0
for ai in a:
    cnt += index - b.sum(d[ai])
    b.add(d[ai]+1, 1)
    index += 1

print(cnt)