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):
import sys
cnt = 0

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

def merge(a, left, mid, right):
	n1 = mid - left
	n2 = right - mid
	L = a[left:left+n1]
	R = a[mid:mid+n2]
	L.append(sys.maxsize)
	R.append(sys.maxsize)
	i = j = 0
	tmp = n1
	for k in range(left, right):
		if L[i] <= R[j]:
			if R[j] != sys.maxsize:
				tmp -= 1
			a[k] = L[i]
			i += 1
		else:
			if L[i] != sys.maxsize:
				global cnt
				cnt += tmp
			a[k] = R[j]
			j += 1		
	
n = int(input())
a = list(map(int, input().split()))
merge_sort(a, 0, len(a))
print(cnt)

Solution (Python):
import sys
cnt = 0

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

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

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

Solution (Python):
import sys
cnt = 0

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

def merge(a, left, mid, right):
	n1 = mid - left
	n2 = right - mid
	L = a[left:left+n1]
	R = a[mid:mid+n2]
	L.append(sys.maxsize)
	R.append(sys.maxsize)
	i = j = 0
	for k in range(left, right):
		if L[i] <= R[j]:
			a[k] = L[i]
			i += 1
		else:
			if i < n1:
				global cnt
				cnt += n1 - i
			a[k] = R[j]
			j += 1
	
n = int(input())
a = list(map(int, input().split()))
merge_sort(a, 0, len(a))
print(cnt)

Solution (Python):
class BIT:
    def __init__(self, n):
        self.bit = [0]*(n+1)
    
    def sumB(self, i):
        s = 0
        while(i>0):
            s+=self.bit[i]
            i -= i & -i
        return s
    
    def addB(self, i, x):
        while(i < len(self.bit)):
            self.bit[i] += x
            i += i & -i
            
n = int(input())
A = [(i+1,int(j)) for i,j in enumerate(input().split())]
A = sorted(A, key=lambda x: x[1])
b = BIT(n)
for i in range(n):b.addB(i+1,1)
ans=0
for i,j in A:
    ans+=b.sumB(i)
    b.addB(i,-1)
print(ans-n)

Solution (Python):
class BIT:
    def __init__(self, n):
        self.bit = [0]*(n+1)
    
    def sumB(self, i):
        s = 0
        while(i>0):
            s+=self.bit[i]
            i -= i & -i
        return s
    
    def addB(self, i, x):
        while(i < len(self.bit)):
            self.bit[i] += x
            i += i & -i
            
n = int(input())
A = [(i+1,int(j)) for i,j in enumerate(input().split())]
A = sorted(A, key=lambda x: x[1])
b = BIT(n)
for i in range(n):b.addB(i+1,1)
ans=0
for i,j in A:
    ans+=b.sumB(i-1)
    b.addB(i,-1)
print(ans)

Solution (Python):



from math import inf

inv = 0


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

    L = A[left:mid]
    L.append(inf)
    R = A[mid:right]
    R.append(inf)
    i = j = 0
    for k in range(left, right):
        if L[i] < R[j]:
            A[k] = L[i]
            i += 1
        else:
            inv += len(L) - i - 1
            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)


def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    merge_sort(A, 0, n)
    print(inv)


main()

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


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

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

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

    def reset(self):
        self.bit = [0] * (self.size + 1)


BIT = BinaryIndexedTree(N)

A_sorted = {a: i for i, a in enumerate(sorted(A), start=1)}
ans = 0
for j, a in enumerate(A):
    ans += j - BIT.sum(A_sorted[a])
    BIT.add(A_sorted[a], 1)

print(ans)

Solution (Python):
n = int(input())
A = [(i + 1, int(j)) for i, j in enumerate(input().split())]
A.sort(key=lambda x: -x[1])

class BIT:
    def __init__(self, n):
        self.data = [0] * (n + 1)
    def add(self, i, x):
        while i <= n:
            self.data[i] += x
            
            i += i & -i

    def get(self, i):
        s = 0
        while i:
            s += self.data[i]
            i -= i & -i
        return s

b = BIT(n)
ans = 0
for i, j in A:
    ans += b.get(i)
    b.add(i, 1)
print(ans)

Solution (Python):
import sys  
import os
import time
import re
from pydoc import help
import string
import math
from operator import itemgetter
from collections import Counter
from collections import deque
from collections import defaultdict as dd
import fractions
from heapq import heappop, heappush, heapify
import array
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy as dcopy
import itertools



sys.setrecursionlimit(10**7)
INF = 10**20
GOSA = 1.0 / 10**10
MOD = 10**9+7
ALPHABETS = [chr(i) for i in range(ord('a'), ord('z')+1)]  
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def DP(N, M, first): return [[first] * M for n in range(N)]
def DP3(N, M, L, first): return [[[first] * L for n in range(M)] for _ in range(N)]
from inspect import currentframe
def dump(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' => '+repr(arg) for arg in args), file=sys.stderr)


def local_input():
    from pcm.utils import set_stdin
    import sys
    from pathlib import Path
    parentdir = Path(os.path.dirname(__file__)).parent
    inputfile = parentdir.joinpath('test/sample-1.in')
    if len(sys.argv) == 1:
        set_stdin(inputfile)




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

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

def pos(a):
    return i

def solve():
    global N,A,bit
    N = int(input())
    A = list(map(int, input().split()))
    bit = [0]*(N+1)

    B = list(set(A))
    B.sort()
    B = [-1] + B

    res = 0
    for i in range(N):
        j = bisect_left(B, A[i])
        res += cum(j)
        add(j, 1)

    print(N*(N-1)//2-res)

    return 0

if __name__ == "__main__":
    try:
        local_input()
    except:
        pass
    solve()

Solution (Python):
import sys
time_check = False
if time_check:
    import time

num_of_inversions = 0
array = [0 for x in range(200000)]

def merge(left, mid, right):
    n_fore = mid - left
    n_rear = right - mid
    l_fore = array[left:left + n_fore]
    l_fore.append(sys.maxsize)
    l_rear = array[mid:mid + n_rear]
    l_rear.append(sys.maxsize)

    i = j = 0
    global num_of_inversions

    offset = len(l_fore) - 1 + left
    for k in range(left, right):
        if l_fore[i] < l_rear[j]:
            array[k] = l_fore[i]
            i += 1
        else:
            array[k] = l_rear[j]
            num_of_inversions += j - k + offset
            
            
            j += 1


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


def main():

    n = int(input())
    for idx, value in enumerate(input().split()):
        array[idx] = int(value)

    if time_check:
        start = time.time()

    merge_sort(0, n)

    if time_check:
        print("elapsed_time:", time.time() - start)

    
    print(num_of_inversions)

    return


main()

Solution (Python):
def InputData():
    
    sequence_len = int(input())
    sequence = [int(a) for a in input().split(" ")]

    return sequence_len, sequence

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

def merge(sequence, left, mid, right):
    global merge_cnt
    n1 = mid - left
    n2 = right - mid
    sequence_left = sequence[left:left + n1]
    sequence_right = sequence[mid:mid + n2]
    sequence_left.append(float('inf'))
    sequence_right.append(float('inf'))

    left_cnt = 0
    right_cnt = 0
    for i in range(left, right):
        if sequence_left[left_cnt] <= sequence_right[right_cnt]:
            
            sequence[i] = sequence_left[left_cnt]
            left_cnt += 1
        else:
            
            sequence[i] = sequence_right[right_cnt]
            right_cnt += 1
            merge_cnt += n1 - left_cnt

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

def PrintOut(cnt):
    print(cnt)

def main():
    [sequence_len, sequence] = InputData()
    
    global merge_cnt
    merge_cnt = 0
    mergeSort(sequence, 0, sequence_len)
    PrintOut(merge_cnt)

if __name__=="__main__":
    main()

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):
    if left+1 < right:
        middle = (left+right)//2
        a = merge_sort(lst,left,middle)
        b = merge_sort(lst,middle,right)
        c = merge(lst,left,middle,right)
        return a+b+c
    return 0

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

Solution (Python):
INF=1000000005
def merge(a,right,mid,left):
    r=a[right:mid]
    l=a[mid:left]
    i=0
    j=0
    q=mid-right
    r.append(INF)
    l.append(INF)
    cnt=0
    while i+j!=left-right:
        if r[i]>l[j]:
            a[right+i+j]=l[j]
            j+=1
            cnt+=q-i
        else:
            a[right+i+j]=r[i]
            i+=1
    return cnt
def mergesort(a,right,left):
    if right+1<left:
        mid=(right+left)//2
        v1=mergesort(a,right,mid)
        v2=mergesort(a,mid,left)
        v3=merge(a,right,mid,left)
        return v1+v2+v3
    else:
        return 0
n=int(input())
a=list(map(int,input().split()))
ans=mergesort(a,0,n)
print(ans)

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 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)

def merge(A,left,mid,right):
    global count
    L = A[left:mid]
    R = A[mid:right]
    L.append(1000000000)
    R.append(1000000000)

    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]
            count += len(L) - i - 1
            j += 1

n = int(input())
nums = list(map(int,input().split(" ")))
count = 0

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

Solution (Python):

import sys
if sys.version_info[0]>=3: raw_input=input

def M(l,r):
	if l+1>=r: return 0
	if l+2==r:
		if A[l]<=A[l+1]: return 0
		A[l],A[l+1]=A[l+1],A[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 A[i]<=A[j]:
			W[k]=A[i]
			k+=1
			i+=1
		else:
			W[k]=A[j]
			k+=1
			j+=1
			c+=m-i
	while i<m:
		W[k]=A[i]
		k+=1
		i+=1
	while j<r:
		W[k]=A[j]
		k+=1
		j+=1
	for i in range(l,r): A[i]=W[i]
	return cl+cr+c

raw_input()
A=list(map(int,raw_input().split()))
W=[0]*len(A)
print(M(0,len(A)))

Solution (Python):

import sys
if sys.version_info[0]>=3: raw_input=input

def M(l,r):
	if l+1>=r: return 0
	if l+2==r:
		if A[l]<=A[l+1]: return 0
		A[l],A[l+1]=A[l+1],A[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 A[i]<=A[j]:
			W[k]=A[i]
			k+=1
			i+=1
		else:
			W[k]=A[j]
			k+=1
			j+=1
			c+=m-i
	while i<m:
		W[k]=A[i]
		k+=1
		i+=1
	while j<r:
		W[k]=A[j]
		k+=1
		j+=1
	for i in range(l,r): A[i]=W[i]
	return cl+cr+c

raw_input()
A=list(map(int,raw_input().split()))
W=[0]*len(A)
print(M(0,len(A)))

Solution (Python):
input()
l=[[int(c)] for c in raw_input().split()]
for i,a in enumerate(sorted(l)):
    a[0]=i+1
s=0
r=len(l)
b=[0]*(1+r)
for n, in reversed(l):
    i=n
    while i>0:
        s+=b[i]
        i&=i-1
    while n<=r:
        b[n]+=1
        n+=n&-n
print s

Solution (Python):
input()
l=[[int(c)] for c in raw_input().split()]
for i,a in enumerate(sorted(l)):
    a[0]=i+1
s=0
r=len(l)+1
b=[0]*r
for n, in reversed(l):
    i=n
    while i>0:
        s+=b[i]
        i&=i-1
    while n<r:
        b[n]+=1
        n+=n&-n
print s

Solution (Python):
input()
l=[[int(c)] for c in raw_input().split()]
for i,a in enumerate(sorted(l)):
    a[0]=i+1
s=0
r=len(l)+1
b=[0]*r
for n, in reversed(l):
    i=n
    while i>0:
        s+=b[i]
        i&=i-1
    while n<r:
        b[n]+=1
        n+=n&-n
print s

Solution (Python):
input()
l=[[int(c)] for c in raw_input().split()]
for i,a in enumerate(sorted(l)):
    a[0]=i+1
s=0
r=len(l)+1
b=[0]*r
for n, in reversed(l):
    i=n
    while i>0:
        s+=b[i]
        i&=i-1
    while n<r:
        b[n]+=1
        n+=n&-n
print s

Solution (Python):
input()
l=[[int(c)] for c in raw_input().split()]
for i,a in enumerate(sorted(l)):
    a[0]=i+1
s=0
r=len(l)+1
b=[0]*r
for n, in reversed(l):
    i=n
    while i>0:
        s+=b[i]
        i&=i-1
    while n<r:
        b[n]+=1
        n+=n&-n
print s

Solution (Python):
input()
l=[[int(c)] for c in raw_input().split()]
for i,a in enumerate(sorted(l)):
    a[0]=i+1
s=0
r=len(l)+1
b=[0]*r
for n, in reversed(l):
    i=n
    while i>0:
        s+=b[i]
        i&=i-1
    while n<r:
        b[n]+=1
        n+=n&-n
print s

Solution (Python):
input()
l=[[int(c)] for c in raw_input().split()]
for i,a in enumerate(sorted(l)):
    a[0]=i+1
s=0
r=len(l)+1
b=[0]*r
for n, in reversed(l):
    i=n
    while i>0:
        s+=b[i]
        i&=i-1
    while n<r:
        b[n]+=1
        n+=n&-n
print s

Solution (Python):
SENTINEL = 10 ** 9 +1
cnt = 0
def merge(A, left, mid, right):
    global cnt

    L = A[left:mid] + [SENTINEL]
    R = A[mid:right] + [SENTINEL]
    
    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
            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 = input()
A = list(map(int, input().split()))
merge_sort(A,0,len(A))
print(cnt)

Solution (Python):
def merge(a, left, mid, right):
    global cnt
    l = a[left:mid] + [sentinel]
    r = a[mid:right] + [sentinel]
    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
            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 = input()
a = list(map(int, input().split()))
sentinel = 10 ** 9 + 1
cnt = 0
merge_sort(a, 0, len(a))
print(cnt)

Solution (Python):
import sys
count = 0
def merge(A, left, mid, right):
    global count
    L = A[left:mid]
    R = A[mid:right]
    L.append(sys.maxint)
    R.append(sys.maxint)
    i = 0
    j = 0
    t = 0
    for k in xrange(left, right):
        if L[i] <= R[j]:
            count += t
            A[k] = L[i]
            i += 1
        else:
            t += 1
            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)

n = int(raw_input())
A = map(int, raw_input().split())
mergeSort(A, 0, n)
print count

Solution (Python):



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

    L.append(float("inf"))
    R.append(float("inf"))
    cnt = 0
    r_id,l_id = 0,0
    for k in range(left,right):
        if(L[l_id] <= R[r_id]):
            A[k] = L[l_id]
            l_id += 1
        else:
            A[k] = R[r_id]
            r_id += 1
            cnt += len(L)-1 - l_id

    return cnt

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

n = int(input())
st = input()
A = list(map(int,st.split()))
ans = margeSort(A,0,n)

print(ans)

Solution (Python):



def merge(array, left, mid, right):
    global cnt
    L = array[left:mid]  + [sentinel]
    R = array[mid:right] + [sentinel]
    i = j = 0

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

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

n = int(input())
numbers = list(map(int, input().split()))
cnt = 0
sentinel = 10 ** 9 + 1
merge_sort(numbers, 0, len(numbers))
print(cnt)

Solution (Python):



def merge(array, left, mid, right):
    global cnt
    L = array[left:mid]  + [SENTINEL]
    R = array[mid:right] + [SENTINEL]
    i = j = 0

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

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

n = int(input())
numbers = list(map(int, input().split()))
cnt = 0
SENTINEL = 10 ** 9 + 1
merge_sort(numbers, 0, len(numbers))
print(cnt)

Solution (Python):
from collections import deque

INFTY = 1e9 + 1


def merge(a, l, m, r):
    global cnt
    ll = deque(a[l:m])
    rl = deque(a[m:r])
    for k in range(l, r):
        if not rl or ll and ll[0] < rl[0]:
            a[k] = ll.popleft()
        else:
            a[k] = rl.popleft()
            cnt += len(ll)


def merge_sort(a, l, r):
    if l + 1 < r:
        m = (l + r) // 2
        merge_sort(a, l, m)
        merge_sort(a, m, r)
        merge(a, l, m, r)


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

Solution (Python):
sentinel = 1000000001

def merge(A, left, mid, right):
    """Merge the two sorted partial sequences A[left:mid] and A[mid:right].

    To count the number of inversions,
    make a global declaration for the variable cnt.
    """
    L = A[left:mid]
    n1 = len(L)
    L.append(sentinel)
    R = A[mid:right]
    R.append(sentinel)
    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
            cnt += (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)


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

cnt = 0

mergeSort(S, 0, n)

print(cnt)

Solution (Python):
sentinel = 1000000001

def merge(A, left, mid, right):
    """Merge the two sorted partial sequences A[left:mid] and A[mid:right].

    To count the number of inversions,
    make a global declaration for the variable cnt.
    """
    L = A[left:mid]
    n1 = len(L)
    L.append(sentinel)
    R = A[mid:right]
    R.append(sentinel)
    i = 0
    j = 0
    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 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())
S = list(map(int, input().split()))

cnt = 0

n_ivs =  mergeSort(S, 0, n)

print(n_ivs)

Solution (Python):
sentinel = 1000000001

def merge(A, left, mid, right):
    L = A[left:mid]
    n1 = len(L)
    L.append(sentinel)
    R = A[mid:right]
    R.append(sentinel)
    i = 0
    j = 0
    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 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())
S = list(map(int, input().split()))

cnt = 0

n_ivs =  mergeSort(S, 0, n)

print(n_ivs)

Solution (Python):
sentinel = 1000000001

def merge(A, left, mid, right):
    L = A[left:mid]
    n1 = len(L)
    L.append(sentinel)
    R = A[mid:right]
    R.append(sentinel)
    i = 0
    j = 0
    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 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())
S = list(map(int, input().split()))

cnt = 0

n_ivs =  mergeSort(S, 0, n)

print(n_ivs)

Solution (Python):
n = int(raw_input())
S = map(int, raw_input().split())

def merge(A, left, mid, right):
    cnt = 0
    n1 = mid - left
    n2 = right - mid
    L = [0] * (n1+1) 
    R = [0] * (n2+1)
    L[:n1] = A[left:mid]
    R[:n2] = A[mid:right]
    
    
    
    
    L[n1] = float('inf')
    R[n2] = float('inf')
    i = 0
    j = 0
    for k in xrange(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 right - left > 1:
        mid = int((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

def main():
    v = mergeSort(S, 0, len(S))
    print v
    return 0

main()

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


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

cnt = 0
input()
num = list(map(int, input().split()))
merge_count(num, 0, len(num))
print(cnt)

Solution (Python):
def merge(A,left,mid,right):
    global ct
    n1=mid-left
    n2=right-mid
    l=[A[left+i] for i in xrange(n1)]
    r=[A[mid+i] for i in xrange(n2)]
    l.append(float('inf'))
    r.append(float('inf'))
    i=0
    j=0
    for k in xrange(left,right):
        if l[i]<=r[j]:
            A[k]=l[i]
            i=i+1
        else:
            A[k]=r[j]
            j=j+1
            ct+=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)

ct=0
n=input()
A=map(int,raw_input().split())
mergesort(A,0,n)
print(ct)

Solution (Python):
import sys

cnt = 0

def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = range(n1 + 1)
    R = range(n2 + 1)

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

    L[n1] = 1000000000
    R[n2] = 1000000000
    i = 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
            cnt += 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__":
    lines = sys.stdin.readlines()
    S = map(int, lines[1].split())
    mergeSort(S, 0, int(lines[0]))
    print cnt

Solution (Python):
from array import array

def merge_sort(A):
    if len(A) <= 1:
        return A, 0
    mid = len(A) // 2
    left, lcount = merge_sort(A[:mid])
    right, rcount = merge_sort(A[mid:])
    merged, count = merge(left, right)
    return merged, lcount + rcount + count

def merge(left, right):
    lpos = 0
    rpos = 0
    rcount = 0
    merged = array('I', [])  
    len_left = len(left)
    len_right = len(right)
    while lpos < len_left and rpos < len_right:
        if left[lpos] < right[rpos]:
            merged.append(left[lpos])
            lpos += 1
        else:
            merged.append(right[rpos])
            rpos += 1
            
            rcount += len_left - lpos
    
    if left[lpos:]:
        merged.extend(left[lpos:])
    if right[rpos:]:
        merged.extend(right[rpos:])
    
    return merged, rcount
    
if __name__ == '__main__':
    n = int(raw_input())
    A = array('I', map(int, raw_input().split()))
    
    sorted, count = merge_sort(A)
    
    print count

Solution (Python):
def merge(A, left, mid, right):
    global count
    banpei = 1000000001
    L = A[left:mid]
    l = len(L)
    L += [banpei]
    R = A[mid:right] + [banpei]

    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 += l - i
    return count


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

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

Solution (Python):


import sys

def merge(A, left, mid, right):
    global count
    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] = R[n2] = sys.maxint
    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 += 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)

n = int(raw_input())
S = map(int, raw_input().split())
count = 0
mergeSort(S, 0, n)
print count

Solution (Python):
cnt = 0
def merge(L,R):
    global cnt
    n = len(L)+len(R)
    lenL = len(L)
    A = []
    i = j = 0
    L.append(10**9+1)
    R.append(10**9+1)
    for _ in range(n):
        if L[i] <= R[j]:
            A.append(L[i])
            i += 1
        else:
            A.append(R[j])
            j += 1
            cnt += lenL-i
    return A

def mergeSort(A):
    if len(A)==1: return A
    m = len(A)//2
    return merge(mergeSort(A[:m]),mergeSort(A[m:])) 

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

Solution (Python):
def invNum(d,A):
    if d < 0 or len(A) < 2: return 0
    cnt = 0
    L = []
    R = []
    for ai in A:
        if ai < 2**d:
            L.append(ai)
            cnt += len(R)
        else:
            R.append(ai-2**d)
    return cnt + invNum(d-1,L) + invNum(d-1,R)
 
if __name__=='__main__':
    n = int(input()) 
    print(invNum(29,list(map(int,input().split()))))