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 partition(A, p, r):
    x = A[r][1]
    i = p-1
    for j in range(p, r):
        if A[j][1] <= x:
            i = i + 1
            (A[i], A[j]) = (A[j], A[i])

    (A[i+1], A[r]) = (A[r], A[i+1])

    return i+1
    
def quicksort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q-1)
        quicksort(A, q+1, r)

def stable(A, B):
    for i in range(len(A)):
        if A[i] != B[i]:
            return "Not stable"
    return "Stable"

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

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

    L.append(10**9)
    R.append(10**9)

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

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

n = int(input())
X = list(map(int, input().split()))
x = mergeSort(X, 0, n)

print(x)

Solution (Python):


def merge(num_list,left,right,cnt):
    mid = (left+right)//2
    L = num_list[left:mid][:]
    R = num_list[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]:
            cnt = cnt + len(L)-i-1
            num_list[k] = R[j]
            j += 1
        else:
            num_list[k] = L[i]
            i += 1
    return cnt

def merge_sort(num_list,left,right,cnt):
    mid = (left+right)//2
    if left+1 < right:
        cnt_l = merge_sort(num_list,left,mid,cnt)
        cnt_r = merge_sort(num_list,mid,right,cnt)
        cnt_all = cnt_l+cnt_r
        cnt = merge(num_list,left,right,cnt_all)

    return cnt

if __name__ == "__main__":
    n = int(input())
    cnt = 0
    num_list = list(map(int,input().split()))
    cnt = merge_sort(num_list,0,len(num_list),cnt)
    print(cnt)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
mod = 10 ** 9 + 7

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 compress(A):
    """ 座標圧縮 """
    zipped, unzipped = {}, {}
    for i, a in enumerate(sorted(set(A))):
        zipped[a] = i
        unzipped[i] = a
    return zipped, unzipped

N = INT()
a = LIST()
x_to_i = {x: i for i, x in enumerate(sorted(set(a)))}
a = [x_to_i[x]+1 for x in a]
ans = 0
bit = Bit(N)

for j in range(N):
    ans += j-bit.sum(a[j])
    bit.add(a[j], 1)
print(ans)

Solution (Python):
inf = 10**9 + 7


def merge(L, R):
    cnt = 0
    l, r = len(L), len(R)
    L.append(inf)
    R.append(inf)
    lst = []
    i, j = 0, 0
    for k in range(l + r):
        if L[i] < R[j]:
            lst.append(L[i])
            i += 1
        else:
            lst.append(R[j])
            j += 1
            
            cnt += l - i
    return lst, cnt


def merge_sort(A):
    l = len(A)
    if l == 1:
        return A, 0
    L, cntL = merge_sort(A[:l // 2])
    R, cntR = merge_sort(A[l // 2:])
    A, cnt = merge(L, R)
    return A, cntL + cntR + cnt


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

Solution (Python):
INFTY=1000000000

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

def merge(A,left,mid,right):
    n1=mid-left
    n2=right-mid
    L=[A[left+i] for i in range(n1)]
    R=[A[mid+i] for i in range(n2)]
    L.append(INFTY)
    R.append(INFTY)
    ans=0
    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
            ans+=max(n1-i,0)
    return ans

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

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

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):
INF = int(1e9)
def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    n = len(A)
    L = A[left:mid] + [INF] 
    R = A[mid:right] + [INF]
    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:
            A[k] = R[j]
            j = j + 1
            cnt = 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

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

Solution (Python):


N = int(input())
S = [int(i) for i in input().split()]
INF = 10**10

def merge(s, l, m, r):
    cnt = 0
    s1 = list(s[l:m])
    s2 = list(s[m:r])

    s1.append(INF)
    s2.append(INF)
    
    i = 0
    j = 0
    for k in range(l, r):
        
        if s1[i] <= s2[j]:
            s[k] = s1[i]
            i += 1
        else:
            s[k] = s2[j]
            j += 1
            cnt += (m - l - i)
    return cnt

def merge_sort(s, l, r, cnt):
    if l + 1 < r:
        m =  (l + r) // 2
    
        cnt = merge_sort(s, l, m, cnt)
        cnt = merge_sort(s, m, r, cnt)
    
        cnt += merge(s, l, m, r)
    return cnt
    
cc = merge_sort(S, 0, len(S), 0)
print(cc)

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

SWAP = 0

def conquer(A, left, mid, right):
  L, R = A[left:mid], A[mid:right]
  
  INFTY = 2 ** 30
  L.append(INFTY)
  R.append(INFTY)
  
  i, j = 0, 0

  swap_times =  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
      swap_times += (mid-left) - i

  return swap_times

def divide(A, left, right):
  

  
  if left+1 < right:
    mid = (left+right)//2

    countL = divide(A, left, mid)
    countR = divide(A, mid, right)

    return conquer(A, left, mid, right) + countL + countR

  return 0

def mergeSort(A):
  return divide(A, 0, len(A))

swap = mergeSort(A)
print(swap)

Solution (Python):
import math
import string
import itertools
import fractions
import heapq
import collections
import re
import array
import bisect
import sys
import random
import time
inf = 10**9


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 = list(map(int, input().split()))

    sorted_a = sorted(a)
    map_a = {}
    for i in range(n):
        map_a[sorted_a[i]] = i
    flat_a = list(map(lambda x: map_a[x], a))
    
    

    bit = BIT(n)
    count = 0
    for i in range(n):
        bit.add(flat_a[i] + 1, 1)
        count = count + i + 1 - bit.sum(flat_a[i] + 1)
    print(count)


if __name__ == '__main__':
    main()

Solution (Python):
global input_n
global input_data
global result


input_n = int(input())
input_data = list(map(int, input().split()))
result = 0


def bubbleSort():
    global result
    for i in range(input_n):
        jude = result
        for j in range(input_n-1, i, -1):
            if input_data[j] < input_data[j-1]:
                input_data[j], input_data[j-1] = input_data[j-1], input_data[j]
                result += 1
        if jude == result: break


def merge(left, mid, right):
    global result
    
    n1 = mid - left
    n2 = right - mid
    inf = 10**9
    L_list = input_data[left: mid] + [inf]
    R_list = input_data[mid: right] + [inf]

    i = 0
    j = 0
    for k in range(left, right):
        if L_list[i] <= R_list[j]:
            input_data[k] = L_list[i]
            i += 1
        else:
            input_data[k] = R_list[j]
            j += 1
            result += n1 - i


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



mergeSort(0, input_n)
print(result)

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):
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))
cnt = 0
inf = float('inf')

def merge_sort(left, right):
    if right-left > 1:
        middle = (left+right) // 2
        merge_sort(left, middle)
        merge_sort(middle, right)
        merge(left, middle, right)

def merge(left, middle, right):
    left_part = A[left:middle]
    right_part = A[middle:right]
    left_part.append(inf)
    right_part.append(inf)
    l, r = 0, 0
    global cnt
    left_size = middle-left
    for i in range(left, right):
        if left_part[l] < right_part[r]:
            A[i] = left_part[l]
            l += 1
        else:
            A[i] = right_part[r]
            cnt += max(left_size-l, 0)
            r += 1

def main():
    merge_sort(0, n)
    print(cnt)

if __name__ == "__main__":
    main()

Solution (Python):
def bitadd(a,w,bit): 
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): 
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret




N = int(input())

a = list(map(int,input().split()))
b = a.copy()
b.sort()
dic = {}

for i in range(N):
    dic[b[i]] = i+1

for i in range(N):
    a[i] = dic[a[i]]

BIT = [0] * (N+1)
ans = 0
a.reverse()

for i in range(N):

    ans += bitsum(a[i],BIT)
    bitadd(a[i],1,BIT)
    

print (ans)

Solution (Python):
cnt = 0
def count(A, left, mid, right):
    L = []
    R = []
    for l in A[left:mid]:
        L.append(l)
    for r in A[mid:right]:
        R.append(r)
    global cnt
    l_idx = 0
    r_idx = 0
    cnt_part = 0
    for i in range(left, right):
        if l_idx >= len(L):
            A[i] = R[r_idx]
            r_idx += 1
            continue
        if r_idx >= len(R):
            A[i] = L[l_idx]
            l_idx += 1
            if l_idx < len(L):
                cnt_part += r_idx
            continue
        if L[l_idx] > R[r_idx]:
            A[i] = R[r_idx]
            cnt_part += 1
            r_idx += 1
        else:
            A[i] = L[l_idx]
            l_idx += 1
            if l_idx < len(L):
                cnt_part += r_idx
    cnt += cnt_part
def count_inversion_number(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        count_inversion_number(A, left, mid)
        count_inversion_number(A, mid, right)
        count(A, left, mid, right)
n = int(input())
A = list(map(int, input().split(' ')))
count_inversion_number(A, 0, n)
print(cnt)

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

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

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

n = int(input())
count = 0
s = list(map(int, input().split()))
mergesort(s, 0, n)
print(count)

Solution (Python):
cnt=0
def merge(A,left,mid,right):
    global cnt
    n1=mid-left
    n2=right-mid
    L=A[left:mid]+[1000000000]
    R=A[mid:right]+[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]
            j+=1
            cnt+=mid -left - i

def mergeSort(A,left,right):
    global cnt

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

    inf = float('inf')
    L = A[left:mid]+[inf]
    R = A[mid:right] + [inf]
    cnt = 0
    n1 = len(L)-1
    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 += n1-i
    return cnt


def mergeSort(A, left, right, count = 0):
    if left+1 < right:
        mid = (left + right)//2
        cnt1 = mergeSort(A, left, mid, count)
        cnt2 = mergeSort(A, mid, right, count)
        cnt3 = merge(A, left, mid, right)
        return cnt1+cnt2+cnt3
    else:
        return 0
n  = int(input())
A = list(map(int, input().split()))
ans = mergeSort(A, 0, n)

print(ans)

Solution (Python):
count = 0

def merge(a, left, mid, right):
    global count
    L = [0] * (mid - left + 1)
    R = [0] * (right - mid + 1)

    for i in range(len(L)):
        if i  == len(L) - 1:
            L[i] = float('inf')
        else:
            L[i] = a[left+i]
    
    for i in range(len(R)):
        if i == len(R) - 1:
            R[i] = float('inf')
        else:
            R[i] = a[mid+i]

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

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)

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

mergeSort(a, 0, l)
print(count)

Solution (Python):
cnt = 0

def merge(a, b):
    global cnt
    c = []
    i = 0
    j = 0
    for k in range(len(a)+len(b)):
        if i < len(a) and j < len(b) and a[i] > b[j]:
            c.append(b[j])
            cnt = cnt + len(a) - i
            j = j + 1
        elif i >= len(a):
            c.append(b[j])
            j = j + 1
        else:
            c.append(a[i])
            i = i + 1
    return c

def mergesort(a):
    if len(a) == 1:
        return a
    else:
        return merge(mergesort(a[:len(a)//2]), mergesort(a[len(a)//2:]))

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

mergesort(a)

print(cnt)

Solution (Python):
n = int(input())

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

c = 0

def merge(A, left, mid, right):
  inf = float('inf')
  L = A[left:mid] + [inf]
  R = A[mid:right] + [inf]
  i = 0
  j = 0
  global c
  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 += 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)

mergesort(S, 0, n)

print(c)

Solution (Python):


class mergeSort:
    def __init__(self, a):
        self.a = a

    def mergeSort(self, left, right):
        if left + 1 < right: 
            middle = (left + right) // 2
            v1 = self.mergeSort(left, middle)
            v2 = self.mergeSort(middle, right)
            v3 = self.merge(left, middle, right)
            return v1 + v2 + v3
        else:
            return 0
    
    def merge(self, left, mid, right):
        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"))
        p = 0 
        q = 0 
        cnt = 0
        for k in range(left, right):
            if l[p] > r[q]: 
                self.a[k] = r[q]
                if l[p] != float("inf"):
                    cnt += (mid - left) - p
                q += 1
            else:
                self.a[k] = l[p]
                p += 1
        return cnt

n = int(input())
a = list(map(int, input().split()))
ms = mergeSort(a)
print(ms.mergeSort(0, n))

Solution (Python):
import math
import sys

_num_inversions = 0

def merge_sort(A, left, right):
    """数列 A を in place に昇順にソートする。

    left は A の先頭のインデックス、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 merge(A, left, mid, right):
    """ソート済みの部分列をマージする。

    数列 A の left から mid - 1 の要素、mid から right - 1 までの
    ２つの部分列はソート済みである。これをマージして、left から right - 1 まで
    ソートする。
    """
    first = A[left:mid]
    first.append(math.inf)  
    second = A[mid:right]
    second.append(math.inf) 

    global _num_inversions
    i = j = 0
    for k in range(left, right):
        if first[i] <= second[j]:
            A[k] = first[i]
            i += 1
        else:
            A[k] = second[j]
            j += 1
            _num_inversions += len(first) - i - 1


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

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

Solution (Python):
class BIT():
    def __init__(self,n):
        self.dat = [0]*(n+1)

    def add(self,a,x):
        i = a
        while i < len(self.dat):
            self.dat[i] = self.dat[i] + x
            i += i & -i

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

n = int(input())
a = list(map(int,input().split()))
b = sorted(a)
tmp = BIT(n)
dic = {}
for i in range(len(b)):
    dic[b[i]] = i+1

ans = 0
for j in range(n):
    ans += j - tmp.sum(dic[a[j]])
    tmp.add(dic[a[j]],1)
print(ans)

Solution (Python):
count = 0


def merge_sort(n, nums):
    global count
    if n == 1:
        return nums
    left_n = n // 2  
    left_sorted = merge_sort(left_n, nums[:left_n]) + [10**9 + 1]  
    right_n = n - left_n
    right_sorted = merge_sort(right_n, nums[left_n:]) + [10**9 + 1]  
    left_idx = 0
    right_idx = 0
    idx = 0
    sorted_list = [0] * n
    while idx < n:
        if left_sorted[left_idx] <= right_sorted[right_idx]:
            sorted_list[idx] = left_sorted[left_idx]
            left_idx += 1
        else:
            sorted_list[idx] = right_sorted[right_idx]  
            if left_sorted[left_idx] <= 10**9 and right_sorted[right_idx] <= 10**9:
                count += left_n - left_idx
            right_idx += 1
        idx += 1
    return sorted_list


def main():
    n = int(input())
    nums = list(map(int, input().split(" ")))
    merge_sort(n, nums)
    print(count)


if __name__ == "__main__":
    main()

Solution (Python):
INF = int(1e18)

def merge(A, left, mid, right):
    L = A[left:mid]
    n1 = len(L)
    R = A[mid:right]
    L.append(INF)
    R.append(INF)
    i, j, count = 0, 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 += n1 - i
    return count

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

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

Solution (Python):

N = int(input())
A = list(map(int,input().split()))
B = []
for i,a in enumerate(A):
    B.append([a,i])
B.sort()
A = [0]*N
for i in range(N):
    bind = B[i][1]
    A[i] = bind+1
    


BIT = [0]*(N+1)
def BIT_SUM(i):
    s = 0
    while i > 0:
        s+=BIT[i]
        i-=i&(-i)
    return s
def BIT_ADD(i,x):
    while i <= N:
        BIT[i]+=x
        i+=i&(-i)
        
ans = 0
for j in range(N):
    ans+=j-BIT_SUM(A[j])
    BIT_ADD(A[j],1)
print(ans)

Solution (Python):


def merge(A, left, mid, right):
    cnt = 0
    n1 = mid - left
    n2 = right - mid
    L = []
    R = []
    for i in range(n1):
        L.append(A[left + i])
    for i in range(n2):
        R.append(A[mid + i])
    L.append(2000000000)
    R.append(2000000000)
    
    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 = 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
        
        

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

Solution (Python):
def merge(A, left, mid, right):
    L = A[left:mid]
    R = A[mid:right]
    NL = len(L)
    NR = len(R)
    i = 0
    j = 0
    ret = 0
    for k in range(left, right):
        if i == NL:
            A[k] = R[j]
            j += 1
        elif j == NR:
            A[k] = L[i]
            i += 1
        elif L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
            ret += NL - i
    return ret


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


def main():
    N, *S = map(int, open(0).read().split())
    ret = mergesort(S, 0, len(S))
    print(ret)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

def merge(numlist, left, mid, right):
    L = numlist[left:mid] + [sys.maxsize]
    R = numlist[mid:right] + [sys.maxsize]
    i = j = 0
    k = left
    inv = 0
    while k < right:
        if L[i] < R[j]:
            numlist[k] = L[i]
            i += 1
        else:
            inv += (mid - left - i)
            numlist[k] = R[j]
            j += 1
        k += 1
    return inv


def cal_inv(numlist, left, right):
    if right > left + 1:
        mid = (left + right) // 2
        linv = cal_inv(numlist, left, mid)
        rinv = cal_inv(numlist, mid, right)
        return linv + rinv + merge(numlist, left, mid, right)
    else:
        return 0
    

if __name__ == '__main__':
    n  = int(input())
    numlist = [int(num) for num in input().split(' ')]
    print(cal_inv(numlist, 0, n))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

class BitSum:
    def __init__(self, n):
        self.n = n + 3
        self.table = [0] * (self.n + 1)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            self.table[i] += x
            i += i & -i

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

def InversionNumber(lst):
    bit=BitSum(max(lst))
    res=0
    for i,a in enumerate(lst):
        res+=i-bit.sum(a)
        bit.update(a,1)
    return res

def main():
    n=int(input())
    aa=list(map(int, input().split()))
    s=set()
    for a in aa:
        s.add(a)
    atob={}
    for i,a in enumerate(sorted(s)):
        atob[a]=i+1
    bb=[]
    for a in aa:
        bb.append(atob[a])
    
    print(InversionNumber(bb))

main()

Solution (Python):

INF = 1e11

def merge(A, left, mid, right):
    n_inv = 0
    L = A[left:mid] + [INF]
    R = A[mid:right] + [INF]
    len_L = len(L) - 1

    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
            n_inv += len_L - i
    return n_inv


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

if __name__ == "__main__":
    n = int(input())
    A = [int(i) for i in input().split()]
    print(merge_sort(A, 0, n))

Solution (Python):
def merge(A,left,mid,right):
    global cnt
    inf=float("inf")
    L=A[left:mid]+[inf]
    R=A[mid:right]+[inf]
    length=len(L)-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
            cnt +=length-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):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for k in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for k in range(c)] for k in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class BIT:
    """ Binary Indexed Tree """

    def __init__(self, n):
        
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def get(self, l, r=None):
        """ 区間和の取得 [l, r) """
        
        if r is None: r = l + 1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

def compress(A):
    """ 座標圧縮 """

    zipped, unzipped = {}, {}
    for i, a in enumerate(sorted(set(A))):
        zipped[a] = i
        unzipped[i] = a
    return zipped, unzipped

N = INT()
A = LIST()

zipped, _ = compress(A)
bit = BIT(N)
ans = 0
for i in range(N-1, -1, -1):
    a = zipped[A[i]]
    ans += bit.sum(a)
    bit.add(a, 1)
print(ans)

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

def merge(A,l,m,r):
    global c
    L=A[l:m]+[1e10]
    R=A[m:r]+[1e10]
    i,j = 0,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 mergesort(A,l,r):
    if l+1<r:
        m=(r+l)//2
        mergesort(A,l,m)
        mergesort(A,m,r)
        merge(A,l,m,r)
c=0
mergesort(a,0,n)
print(c)

Solution (Python):
cnt=0
def merge_sort(S):
    l=len(S)
    mid=int(l/2)
    Left=S[0:mid]
    Right=S[(mid):l]
    global cnt
    if l>=2:
        merge_sort(Left) and merge_sort(Right)
    Left.append(float('inf'))
    Right.append(float('inf'))
    p=0
    q=0
    for i in range(l):
        if Left[p]<Right[q]:
            S[i]=Left[p]
            p+=1
        else:
            S[i]=Right[q]
            q+=1
            if l>1 and len(Left)-1>=p and Left[p]!=float('inf'):
                cnt+=len(Left)-p-1
    return S



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

merge_sort(A)
print(cnt)

Solution (Python):
count=0
def merge(A,left,mid,right):
    global count
    L=A[left:mid]+[10**9+1]
    R=A[mid:right]+[10**9+1] 
    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 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=[int(i) for i in input().split()]
mergeSort(S,0,n)
print(count)