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

"""
ソートテク関連の基本的な関数の詰め合わせ (命名は C++ STL algorithm による)


stable_partition(seq, func):
    O(n)
    空間計算量も O(n)
    述語が True を返す全ての要素が、述語が False を返す全ての要素よりも前になるようにシーケンスを並び替える (破壊、安定)


nth_element(seq, k, begin, end):
    O(n)
    E = seq[k] とする
    特定の要素 E よりも小さい全ての要素が E よりも前になり、 E 以上の全ての要素がEよりも後になるように seq[begin:end] を並び替える (破壊、不安定)
    heapq の nlargest とは異なるので注意


ith_order_statistic(seq, i, begin, end):
    O(n)
    nth_element を用いて (seq[begin:end] に存在することがわかっている) i 番目の順序統計量を求める (i = 0, 1, ..., n-1)


simple_quick_sort(seq, begin, end):
    O(nlgn)
    nth_element を用いて seq[begin:end] をソートする (破壊、不安定)


modified_merge_sort(seq, begin, end):
    O(nlgn)
    _modified_merge を用いて seq[begin:end] をソートする (非破壊、安定)
    転倒数とソート済み配列を返す


count_inversion(seq):
    O(nlgn)
    modified_merge_sort を用いて seq の転倒数を求める
    (転倒数: seq[i] > seq[j] (i < j) なる (i, j) の組み合わせの数のこと)
"""


import random
from typing import TypeVar, Callable, List, Tuple, Union
T = TypeVar('T')
Num = Union[int, float]




def _modified_merge(left: List[Num], right: List[Num]) -> Tuple[int, List[Num]]:
    """
    ソート済み配列 left, right を受け取り、全体のソート済み配列を生成する (O(n))
    マージの過程で転倒数をメモして返す

    Args:
        left (list): ソート済み
        right (list): ソート済み

    Returns:
        inv (int): 転倒数
        sorted_list (list): ソート済み
    
    Examples:
        >>> _modified_merge([1, 5, 7], [2, 3, 3])
        (6, [1, 2, 3, 3, 5, 7])
    """
    sorted_list = []
    i, j, inv = 0, 0, 0
    buf_1 = left[:] + [float('inf')]
    buf_2 = right[:] + [float('inf')]
    for _ in range(len(left) + len(right)):
        if buf_1[i] < buf_2[j]:
            sorted_list.append(buf_1[i])
            i += 1
            inv += j
        else:
            sorted_list.append(buf_2[j])
            j += 1
    return inv, sorted_list


def modified_merge_sort(L, begin, end):
    """
    L[begin:end] を 非破壊的かつ安定にマージソートする (O(nlgn))
    マージソートの過程で転倒数をメモして返す

    Args:
        L (list)
        begin, end (int)
    
    Returns:
        inv (int): 転倒数
        sorted_list (list): ソート済み
    
    Examples:
        >>> modified_merge_sort([3, 5, 2, 1, 0], 0, 5)
        (9, [0, 1, 2, 3, 5])
    """
    if end - begin == 1:
        return 0, [L[begin]]
    mid = (begin + end) // 2
    left_inv_cnt, left = modified_merge_sort(L, begin, mid)
    right_inv_cnt, right = modified_merge_sort(L, mid, end)
    merge_inv_cnt, sorted_list = _modified_merge(left, right)
    return left_inv_cnt + right_inv_cnt + merge_inv_cnt, sorted_list


def count_inversion(L):
    """
    modified_merge_sort() を用いて L の要素の転倒数を求める (O(nlgn))

    Examples:
        >>> count_inversion([1, 9, 2, 7, 5, 6, 4, 8, 3, 0])
        26
    """
    cnt, _ = modified_merge_sort(L, 0, len(L))
    return cnt


if __name__ == "__main__":
    n = int(input())
    L = list(map(int, input().split()))
    print(count_inversion(L))

Solution (Python):
def merge(cnt, A, left, mid, right):
    L = A[left:mid] + [2147483648]
    R = A[mid:right] + [2147483648]
    i = 0
    j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
            cnt.append(j)
        else:
            A[k] = R[j]
            j += 1
            
def mergeSort(cnt, A, left, right):
    if left+1 < right:
        mid = (left + right) // 2
        mergeSort(cnt, A, left, mid)
        mergeSort(cnt, A, mid, right)
        merge(cnt, A, left, mid, right)
        
        
import sys
def input():
    return sys.stdin.readline()[:-1]
    
n = int(input())
S = list(map(int, input().split()))

from collections import deque
cnt = deque()
mergeSort(cnt,S,0,n)

print(sum(cnt))

Solution (Python):
def merge(A, l, m, r):
    cnt = 0  
    n1 = m-l 
    n2 = r-m  

    L = A[l:m]  
    L.append(float("inf")) 
    R = A[m:r]
    R.append(float("inf")) 

    i_l, i_r = 0, 0  
    for k in range(l, r):
        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, l, r):
    if l + 1 >= r:  
        return 0

    m = (l+r)//2
    ans1 = merge_sort(A, l, m)  
    ans2 = merge_sort(A, m, r)
    ans3 = merge(A, l, m, r)  

    return ans1 + ans2 + ans3


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

Solution (Python):
class BIT_dinamic: 
    def __init__(self, n):
        self.tree = {}
        self.MAX = n
    def get_sum(self, i): 
        s = 0; i += 1
        while i > 0:
            if i in self.tree:
                s += self.tree[i]
            i -= i & -i
        return s
    def query(self,l,r): 
        return self.get_sum(r) - self.get_sum(l-1) 
    def add(self, i, x):
        i += 1
        while i <= self.MAX:
            if i in self.tree:
                self.tree[i] += x
            else:
                self.tree[i] = x
            i += i & -i

   

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

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

sA = sorted(a)



b = BIT_dinamic(n)

from bisect import *
ans = 0
for i,ai in enumerate(a):
    j = bisect_left(sA, ai)
    ans += i - b.get_sum(j)
    b.add(j,1)

print(ans)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    n = I()
    S = LI()

    def merge_cnt(A, left, mid, right):
        L = A[left:mid]
        R = A[mid:right]
        L.append(INF)
        R.append(INF)
        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]
                cnt += (mid - left) - i
                j += 1
        return cnt

    def rec(A, left, right):
        if left+1 < right:
            mid = (left+right)//2
            l_cnt = rec(A, left, mid)
            r_cnt = rec(A, mid, right)
            m_cnt = merge_cnt(A, left, mid, right)
            return l_cnt+r_cnt+m_cnt
        else:
            return 0

    print(rec(S, 0, n))

if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
MAX = 2*10**5
SENTINEL = 2*10**9
L = [0]*(MAX//2 + 2)
R = [0]*(MAX//2 + 2)

def Merge(A,n,left,mid,right):
    cnt = 0
    n1 = mid - left
    n2 = right - mid
    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]
    
    L[n1] = SENTINEL
    R[n2] = SENTINEL
    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 += n1 - i
    return cnt

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

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

Solution (Python):
n=int(input())
nums=list(map(int,input().split()))
count=0

def inversions(nums,left,mid,right):
    global count
    inf=10**9
    L=nums[left:mid]+[inf]
    R=nums[mid:right]+[inf]
    i=0
    j=0
    l=len(L)-1
    for k in range(left,right):
        if L[i]<=R[j]:
            nums[k]=L[i]
            i+=1
            l-=1

        else:
            nums[k]=R[j]
            j+=1
            count+=l


def inversions_sort(nums,left,right):
    if left+1<right:
        mid=(left+right)//2
        inversions_sort(nums,left,mid)
        inversions_sort(nums,mid,right)
        inversions(nums,left,mid,right)



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

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

class BinaryIndexedTree():

    def __init__(self,init_val):
        self.bit = [0] + init_val
        self.n  = len(init_val)

    def sum(self,i):
        ret = 0
        while i > 0:
            ret += self.bit[i]
            i -= (i & -i)
        return ret
    
    def add(self,i,x):
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)

def main():
    N = int(input())
    A = list(map(int,input().split()))
    B = sorted(A)
    dic = {b:i for i,b in enumerate(B,1)}
    bit = BinaryIndexedTree([0]*N)
    ans = 0
    for i,a in enumerate(A):
        ans += i - bit.sum(dic[a])
        bit.add(dic[a],1)
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
import math
inf = 1000000001

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

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

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


n_ivs = mergeSort(A,0,n)


print(n_ivs)

Solution (Python):
n = int(input())
S = [int(i) for i in input().split()]
infty = 10**10
cnt = 0
def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    
    L = A[left:mid] + [infty]
    R = A[mid:right] + [infty]
    
    i = 0
    j = 0
    for k in range(left, right):
        global cnt
        if(L[i] <= R[j]):
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
            if(L[i] != infty):

                cnt += len(L) - 1  - 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)
mergeSort(S, 0, len(S))

print(cnt)

Solution (Python):

import sys

sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read
inp = sys.stdin.buffer.readline


def inpS(): return inp().rstrip().decode()


readlines = sys.stdin.buffer.readlines
MOD = 10 ** 9 + 7
INF = 1 << 60





cnt = 0
def resolve():
    def merge(l, r):
        global cnt
        mA = []
        l_i = 0
        r_i = 0
        while l_i < len(l) and r_i < len(r):
            if l[l_i] <= r[r_i]:
                mA.append(l[l_i])
                l_i += 1
            else:
                mA.append(r[r_i])
                r_i += 1
                
                cnt += len(l) - l_i
        
        if l_i < len(l):
            mA.extend(l[l_i:])
        elif r_i < len(r):
            mA.extend(r[r_i:])
        return mA

    def mergesort(arr):
        if len(arr) <= 1:
            return arr
        mid = len(arr) // 2
        left = mergesort(arr[:mid])
        right = mergesort(arr[mid:])

        return merge(left, right)

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

    mergesort(A)
    print(cnt)

if __name__ == '__main__':
    resolve()

Solution (Python):
def get_num_inversions(A, left, right):
    num_inversions = 0
    if right - left <= 1:
        return num_inversions

    mid = (left+right) // 2
    num_inversions += get_num_inversions(A, left, mid)
    num_inversions += get_num_inversions(A, mid, right)
    num_inversions = merge(A, left, mid, right, num_inversions)

    return num_inversions


def merge(A, left, mid, right, num_inversions):
    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(1e10)
    R.append(1e10)

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

    return num_inversions


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


if __name__ == '__main__':
    main()

Solution (Python):
cnt = 0
n = int(input())
S = list(map(int, input().split()))

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)

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

  L = S[left:mid] + [10**10]
  R = S[mid:right] + [10**10]

  i,j = 0,0

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

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

Solution (Python):
MAX = 200000
INF = 10 ** 10
cnt = 0


def merge(A, left, mid, right):
    global cnt
    L = A[left:mid] + [INF]
    R = A[mid:right] + [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
          cnt += mid - left - i
    return cnt

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

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

Solution (Python):
def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid]
    R = A[mid:right]
    L.append(10 ** 9)
    R.append(10 ** 9)
    i = 0
    j = 0
    global count
    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 = int((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()))
count = 0
mergeSort(A, 0, n)

print(count)

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

from collections import defaultdict

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
 












bit = BIT(n)

b = sorted(a)


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


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

print(ans)

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

  l = array[left:mid]
  r = array[mid:right]

  l.append(9999999999)
  r.append(9999999999)

  i, j = 0, 0

  for k in range(left, right):
    if l[i] <= r[j]:
      array[k] = l[i]
      i += 1
    else:
      array[k] = r[j]
      cnt += n1 - i
      j += 1
  
  return cnt

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

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

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 math

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


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

A_out, cnt_out = mergeSort(A,0,len(A),0)

print(str(cnt_out))

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

Solution (Python):
INF = pow(10, 18)

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

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

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

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

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

cnt = 0

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

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


def mergeSort(A,left,right):

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

mergeSort(A,0,n)

print(cnt)

Solution (Python):
n=int(input())
A=tuple(map(int,input().split()))
cnt=0
def merge_sort(A,n):
    if n == 1:
        return A
    else:
        global cnt
        mid=(n+1)//2
        nl=len(A[:mid])
        nr=len(A[mid:])
        L=merge_sort(A[:mid],nl)
        R=merge_sort(A[mid:],nr)
        nli=0
        nri=0
        ans=[0]*(nl+nr)
        i=0
        while i < n:
            if nli == nl:
                ans[i]=R[nri]
                nri += 1
            elif nri == nr:
                ans[i]=L[nli]
                nli += 1
            elif L[nli] <= R[nri]:
                ans[i]=L[nli]
                nli += 1
            else:
                ans[i]=R[nri]
                nri += 1
                cnt += nl-nli
            i += 1
        return tuple(ans)
                



merge_sort(A,n)
print(cnt)

Solution (Python):
N = int(input())
A = [int(a) for a in input().split()]

snt = 10 ** 9 + 1

def merge(A, left, mid, right):
    cnt = 0
    L = A[left:mid] + [snt]
    R = A[mid:right] + [snt]
    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 += len(L) - 1 - i
    return cnt

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

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

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



SENTINEL = 10 ** 9 + 1



L = [0] * (n // 2 + 2)
R = [0] * (n // 2 + 2)

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

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

cnt = 0

merge_sort(A, 0, n)

print(cnt)

Solution (Python):
def merge(arr, l, mid, r):
    L = [arr[i] for i in range(l, mid)]
    R = [arr[i] for i in range(mid, r)]
    L.append(int(1e9 + 10))
    R.append(int(1e9 + 10))
    i, j = 0, 0
    cnt = 0
    for k in range(l, r):
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
            cnt += len(L) - i -1
    return cnt

def mergeSort(arr, l, r):
    cnt = 0
    if l + 1 < r:
        mid = (l + r) >> 1
        cnt += mergeSort(arr, l, mid)
        cnt += mergeSort(arr, mid, r)
        cnt += merge(arr, l, mid, r)
    return cnt

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

Solution (Python):
n = int(input())
S = list(map(int, input().split()))
c = 0


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


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)


merge_sort(0, n)

print(c)

Solution (Python):
c = 0

def merge(a,l,m,r):
    global c
    n1 = m-l
    n2 = r-m
    L = a[l:m]
    R = a[m:r]
    L.append(1000000009)
    R.append(1000000009)
    i,j = 0,0
    for k in range(l,r):
        if L[i]<R[j]:
            a[k] = L[i]
            i += 1
        else :
            a[k] = R[j]
            j += 1
            c += n1-i

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

def main():
    n = int(input())
    a = list(map(int,input().split()))
    mergeSort(a,0,n)
    print (c)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


class BinaryIndexTree:  
    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


if __name__ == "__main__":
    N = int(input())
    bit = BinaryIndexTree(N+10)

    A = list(map(int, input().split()))
    d = {a: i+1 for i, a in enumerate(sorted(A))}

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

Solution (Python):
INF = 10**9 + 1
def merge(A: list, left: int, mid: int, right: int) -> int:
  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):
inv_count = 0

def Merge(A, left, mid, right):
    global inv_count

    sentinel = 2000000000
    n1 = mid - left
    n2 = right - mid
    L = A[left : left + (mid - left)] + [sentinel] 
    R = A[mid : mid + (right - mid)] + [sentinel]
    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
            inv_count += (n1 - 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)

def Main():
    N = input()
    A = [int(a) for a in input().split()]
    MergeSort(A, 0, len(A))
    global inv_count
    print(inv_count)

Main()

Solution (Python):
class BIT:
    def __init__(self, n, init=None):
        self.size = n
        if init is None:
            self.bit = [0] * (n + 1) 
        else:
            self.bit = [0] + init
            for i in range(1, n):
                self.bit[i + (i & -i)] += self.bit[i]

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

    def add(self, i, x):
        '''
        set bit[i] to be bit[i] + x
        '''
        assert i > 0
        while i <= self.size:
            self.bit[i] += x
            i += i & -i

def coord_compress(A):
    B = {a: i for i, a in enumerate(sorted(set(A)))}
    return [B[a] for a in A]
    
def inversion_number(A):
    inv = 0
    bit = BIT(len(A))
    for i, x in enumerate(coord_compress(A)):
        inv += i - bit.sum(x+1)
        bit.add(x+1, 1)
    return inv

N = int(input())
*A, = map(int, input().split())
print(inversion_number(A))

Solution (Python):

N = int(input())
A = list(map(int, input().split()))
INF = float('inf')
cnt = 0


def merge(left, mid, right):
    global cnt
    L = A[left:mid]+[INF]
    R = A[mid:right]+[INF]
    l = 0
    r = 0
    nl = mid - left

    for i in range(right-left):
        if L[l] < R[r]:
            A[left+i] = L[l]
            l += 1
        else:
            A[left+i] = R[r]
            r += 1
            cnt += nl - l


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)


merge_sort(0, N)
print(cnt)

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

Solution (Python):
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))