Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

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



Sample input:
5
3 5 2 1 4


Sample output:
6

Submission status: Accepted

Solution code:
n = int(input())
nlist = list(map(int, input().split()))
W = [0for i in range(n)]
def M(l,r):      ##l~r-1 까지의 리스트.
    if (l+1 >= r):
        return 0
    elif (l+2 == r):
        if (nlist[l] <= nlist[l+1]):
            return 0
        else:
            nlist[l],nlist[l+1] = nlist[l+1],nlist[l]
            return 1
    ##위의 if문으로 (r-l)가 2이하일 경우는 해놓음
    m = (l+r)//2
    i = l
    j = m
    k = l
    cl = M(l,m)
    cr = M(m,r)
    c = 0
    while (i<m and j<r):
        if (nlist[i] <= nlist[j]):
            W[k] = nlist[i] ##l부터 r까지 W에 크기순으로 대입해나감
            k += 1
            i += 1
        else:
            W[k] = nlist[j]  ##일단 W[k]에는 더 작은쪽을 저장하는듯
            k += 1
            j += 1
            c += (m-i)  ##만약 nlist[i] > nlist[j]라면 i~m-1 까지 반전 하고있기 때문
                        ##그러고 더 작은 nlist[j]를 안에 넣는것.
    while (i<m):   ##i번째쪽에 더 큰것들이 남았을 경우 (j=r 이 되있는 상황이기에 더 반전수를 늘리지는 않음)
        W[k] = nlist[i]
        k += 1
        i += 1
    while (j<r):   ##j쪽에 큰게 남아있는경우도 동일
        W[k] = nlist[j]
        k += 1
        j += 1
    for i in range(l,r): 
        nlist[i] = W[i]
    return cl+cr+c
        
print(M(0,n))

Submission status: Accepted

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

def merge(A, left, mid, right):
    num = 0 # the number of inversion between two subarrays L and R    
    n1 = mid - left
    n2 = right - mid
    L = [0]*(n1+1)
    R = [0]*(n2+1)
    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]
    L[n1] = float("inf")
    R[n2] = float("inf")
    i = 0
    j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            num += n1 - i
            A[k] = R[j]
            j += 1
    return num
            
def merge_sort(A, left, right):
    if not(left + 1 < right):
        num = 0
    else:
        mid = (left + right)//2
        num_left = merge_sort(A, left, mid)
        num_right = merge_sort(A, mid, right)
        num_merge = merge(A, left, mid, right)
        num = num_left + num_right + num_merge
    return num

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
def merge(a, left, mid, right):
    cnt = 0
    n1 = mid - left
    n2 = right - mid
    l = a[left:left+n1]
    r = a[mid:mid+n2]
    l.append(float('inf'))
    r.append(float('inf'))
    i = 0
    j = 0
    for k in range(left, right):
        if l[i] <= r[j]:
            a[k] = l[i]
            i += 1
        else:
            a[k] = r[j]
            j += 1
            cnt += n1 - i
    return cnt


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


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

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

Submission status: Accepted

Solution code:
# Recursion / Divide and Conquer - The Number of Inversions
def conq(A,left,mid,right):
    global c
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid] + [10**9+1]
    R = A[mid:right] + [10**9+1]
    i,j = 0,0
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
            c += n1 - i

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

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

Submission status: Runtime Error

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


BIT = BinaryIndexedTree(N)
ans = 0
for j in range(N):
    ans += j - BIT.sum(A[j])
    BIT.add(A[j], 1)
print(ans)

Submission status: Runtime Error

Solution code:
rom collections import deque
n = int(input())
nd = deque(map(int, input().split()))
c = 0
for i in range(n):
    m = min(nd)
    s = nd.popleft()
    if (s != m):
        for k in nd:
            if (k < s):
                c += 1
    
print(c)

Submission status: Runtime Error

Solution code:
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>

#define REP(i, n) for (int i = 0; i < (n); i++)
#define FOR(i, init, n) for(int i = init; i < (n); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define Cout(obj) cout << obj << endl
#define Size(obj) (int)(obj).size()
#define fcout cout << fixed << setprecision(10)
#define fi first
#define se second

using namespace std;
using ll = long long int;
using P = pair<int, int>;
using T = tuple<int, int, int>;
using edge = struct
{
    int to, cost;
};

const int MOD = 1e9 + 7;
const int iINF = 1e9;
const long long int llINF = 1e18;
const double PI = acos(-1.0);

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

template <typename T>
class BIT
{
  private:
    vector<T> array;
    int N;

  public:
    BIT(int size) : array(size + 1, 0), N(size) {}

    T sum(int i)
    {
        T sum = 0;
        while (i > 0)
        {
            sum += array[i];
            i -= i & -i;
        }

        return sum;
    }

    T sum(int l, int r)
    {
        T res_l = sum(l - 1);
        T res_r = sum(r);

        return res_r - res_l;
    }

    void add(int i, T x)
    {
        while (i <= N)
        {
            array[i] += x;
            i += i & -i;
        }
    }

    int lower_bound(int w)
    {
        if (w <= 0)
        {
            return 0;
        }        

        int init = 1;
        while(init < N)
        {
            init *= 2;
        }

        int x = 0;
        for(int k = init; k > 0; k /= 2)
        {
            if(x + k <= N && array[x + k] < w)
            {
                w -= array[x + k];
                x += k;
            }
        }
        
        return x + 1;
    }
};

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N;
    cin >> N;
    vector<int> a(N);
    BIT<int> bit(N);
    REP(i, N)
    {
        cin >> a[i];
    }

    ll ans = 0;
    REP(i, N)
    {
        ans += bit.sum(a[i], N);
        bit.add(a[i], 1);
    }

    Cout(ans);

    return 0;
}

Submission status: Runtime Error

Solution code:
# 5
# 3 5 2 1 4
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 solve():
    global N,A,bit
    N = int(input())
    A = list(map(int, input().split()))
    bit = [0]*(N+1)

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

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

    return 0

if __name__ == "__main__":# {{{
    try:
        local_input()
    except:
        pass
    solve()
# vim: set foldmethod=marker:}}}

Submission status: Runtime Error

Solution code:
# 5
# 3 5 2 1 4
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 solve():
    global N,A,bit
    N = int(input())
    A = list(map(int, input().split()))
    bit = [0]*(N+1)

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

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

    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
import std.array, std.stdio, std.conv, std.string, std.math, std.random, std.range,std.functional;
import std.algorithm.searching, std.algorithm.sorting, std.algorithm.iteration, std.algorithm.comparison;
 
int count;
 
void main()
{
    readln();
    int[] list = readln().split.to!(int[]);
    writeln(count);
}
 
int[] merge(int[] a, int[] b)
{
    int[] res;
    res.reserve(a.length+b.length);
    while(a.length != 0 && b.length != 0)
    {
        if(a.front < b.front)
        {
            res ~= a.front;
            a.popFront();
        }else{
            count+=a.length;
            res ~= b.front;
            b.popFront();
        }
    }
    res ~= a ~ b;
    return res;
}
 
int[] mergeSort(int[] list)
{
    if(list.length == 0)
        return list;
    if(list.length == 1)
        return list;
    auto mid = list.length / 2;
    auto a = mergeSort(list[0..mid]);
    auto b = mergeSort(list[mid..$]);
    return merge(a, b);
}
 
sizediff_t minIndex(alias pred="a<b", R) (R list)
    if(isForwardRange!R && !isInfinite!R && is(typeof(binaryFun!pred(list.front, list.front))))
{
    assert(!list.empty);
    typeof(list.front) min = list.front;
    sizediff_t minPos;
    sizediff_t curPos;
    for(list.popFront(); !list.empty; list.popFront())
    {
        curPos++;
 
        if(binaryFun!pred(list.front, min))
        {
            min = list.front;
            minPos = curPos;
        }
    }
    return minPos;
}

Submission status: Runtime Error

Solution code:
import std.array, std.stdio, std.conv, std.string, std.math, std.random, std.range,std.functional;
import std.algorithm.searching, std.algorithm.sorting, std.algorithm.iteration, std.algorithm.comparison;
 
long count;
 
void main()
{
    readln();
    int[] list = readln().split.to!(int[]);
    mergeSort(list);
    writeln(count);
}
 
int[] merge(int[] a, int[] b)
{
    int[] res;
    res.reserve(a.length+b.length);
    while(a.length != 0 && b.length != 0)
    {
        if(a.front < b.front)
        {
            res ~= a.front;
            a.popFront();
        }else{
            count+=a.length;
            res ~= b.front;
            b.popFront();
        }
    }
    res ~= a ~ b;
    return res;
}
 
int[] mergeSort(int[] list)
{
    if(list.length == 0)
        return list;
    if(list.length == 1)
        return list;
    auto mid = list.length / 2;
    auto a = mergeSort(list[0..mid]);
    auto b = mergeSort(list[mid..$]);
    return merge(a, b);
}
 
sizediff_t minIndex(alias pred="a<b", R) (R list)
    if(isForwardRange!R && !isInfinite!R && is(typeof(binaryFun!pred(list.front, list.front))))
{
    assert(!list.empty);
    typeof(list.front) min = list.front;
    sizediff_t minPos;
    sizediff_t curPos;
    for(list.popFront(); !list.empty; list.popFront())
    {
        curPos++;
 
        if(binaryFun!pred(list.front, min))
        {
            min = list.front;
            minPos = curPos;
        }
    }
    return minPos;
}

Submission status: Runtime Error

Solution code:
global cnt = 0
def modify_order(A):
  if len(A) < 2:
    return
  *B, hip, tail = A
  if (hip > tail):
    cnt += 1
    return modify_order(B + [tail])+ [hip]
  else:
    return modify_order(B + [hip])+ [tail]

def sort(A):
  if len(A) < 2:
    return A
  head, *B = modify_order(A)
  return [head] + sort(B)
  
n = int(input())
*A, = map(int, input().split())
sort(A)

print(cnt)

Submission status: Runtime Error

Solution code:
class Bit:
    def __init__(self, size):
        self.arr = [0] * (size + 1)
        self.size = size

    def read(self, index):
        sum_b = 0
        while index:
            sum_b += self.arr[index]
            index &= index - 1
        return sum_b

    def update(self, index, value=1):
        while index <= self.size:
            self.arr[index] += value
            index += index & -index


bit, a, inv = Bit(int(input())), list(map(int, input().split())), 0

for i in reversed(a):
    inv += bit.read(i)
    bit.update(i)
print(inv)

Submission status: Runtime Error

Solution code:
def num_of_inversions(A, n, cnt = 0):
    """Return the number of inversions in the sequence A.

    A is a list of numbers.
    n is the length of A.
    cnt is a accumulator.
    """

    if n == 1:
        return cnt
    t_cnt = 0
    t_lt = A[-1]
    for i in reversed(A[:n - 1]):
        if i > t_lt:
            t_cnt += 1
    return num_of_inversions(A[:n - 1], n - 1, cnt + t_cnt)


import sys

n = int(sys.stdin.readline())

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

ans = num_of_inversions(A, n)

print(ans)

Submission status: Runtime Error

Solution code:
import numpy

def countInversions(A, cnt):
    if len(A) == 1:
        return cnt

    maxi = numpy.argmax(A)
    cnt += len(A) - maxi - 1
    del A[maxi]
    return countInversions(A, cnt)

if __name__ == "__main__":
    input()
    A = map(int, raw_input().split())
    print countInversions(A, 0)

Submission status: Runtime Error

Solution code:
def countInversions(A, cnt):
    if len(A) == 1:
        return cnt

    maxi = argmax(A)
    cnt += len(A) - maxi - 1
    del A[maxi]
    return countInversions(A, cnt)

def argmax(A):
    max = maxi = 0
    for i in range(len(A)):
        if A[i] > max:
            max = A[i]
            maxi = i
    return maxi

if __name__ == "__main__":
    input()
    A = map(int, raw_input().split())
    print countInversions(A, 0)

Submission status: Runtime Error

Solution code:
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.array('B', [])  # List is too slow, so use array instead
    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.array('B', map(int, raw_input().split()))
    
    sorted, count = merge_sort(A)
    #print ' '.join(str(x) for x in sorted)
    print count

Submission status: Runtime Error

Solution code:
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.array('h', [])  # List is too slow, so use array instead
    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.array('h', map(int, raw_input().split()))
    
    sorted, count = merge_sort(A)
    #print ' '.join(str(x) for x in sorted)
    print count

Submission status: Runtime Error

Solution code:
from collections import deque

n = int(input())
A = deque(map(int, input().split()))
num = list(sorted(A, reverse=True))

count = 0
for i in range(n - 1):
    count += len(A) - 1 - A.index(num[i])
    A.remove(num[i])

print(count)

Submission status: Runtime Error

Solution code:
from collections import deque
n = int(input())
A = deque(map(int, input().split()))
num = list(sorted(A, reverse=True))

count = 0
for i in range(n - 1):
    count += len(A) - 1 - A.index(num[i])
    A.remove(num[i])

print(count)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

n = int(raw_input())
A = map(int, raw_input().split())
count = 0
for i in range(n):
    for j = in range(i, n):
        if A[i] > A[j]:
            count += 1
print count

Submission status: Runtime Error

Solution code:
def invNum(A):
    if len(A)==1: return 0
    cnt = 0
    for i in range(1,len(A)):
        if A[0] > A[i]: cnt += 1
    return cnt + invNum(A[1:])


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

Submission status: Runtime Error

Solution code:
def bubble_sort_revision(target_list):

    list_length = len(target_list)
    
    flag = True
    change_count = 0
    
    for top_index in range(1,list_length):
        for i in range(top_index, list_length)[::-1]:
            if target_list[i] < target_list[i - 1] and target_list[top_index] >= target_list[i]:
                tmp = target_list[i]
                target_list[i] = target_list[i - 1]
                target_list[i - 1] = tmp
                change_count += 1
                
    return change_count
def solve(n, target_list):
    a = [0 for i in range(n + 1)]
    ans = 0
    for i in range(n):
        ans += i - sum(a[:target_list[i]])
        a[target_list[i]] += 1
    return ans

if __name__ == "__main__":
    l = int(input())
    target_list = [int(i) for i in input().split()]
    print(solve(l, target_list))

Submission status: Runtime Error

Solution code:
n = int(input())
A = list(map(int, input().split()))
cnt = 0

for i in range(n):
    for j in range(i+1, n):
        if A[i] > A[j]:
            cnt++

print(cnt)

Submission status: Runtime Error

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

    n1 = mid-left
    n2 = right-mid
    #L = [0 for i in range(n1+1)]
    #R = [0 for i in range(n2+1)]
    #for i in range(n1):
    #    L[i] = A[left+i]
    #for i in range(n2):
    #    R[i] = A[mid+i]
    L = A[left:mid]
    R = A[mid:right]
    L.append(float('inf'))
    R.append(float('inf'))
    i = 0
    j = 0
    global cnt

    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 += l-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)
    else:
        return 0

n = input()
A = list(map(int, input().split()))
cnt = 0
mergeSort(A, 0, len(A))
#print(*A)
print(str(cnt))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

def main():
    """ ????????? """
    num = int(input().strip())
    A = list(map(int,input().split()))
    cnt = 0
    for i in range(num-1):
        for j in range(i,num):
            if i > j:
                cnt++
    if cnt % 2 == 0:
        cnt += 1
    else:
        cnt -= 1
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
A = tuple(map(int, input().split()))
print(len(1 for i in range(N - 1) for j in range(i + 1, N) if A[i] > A[j]))

Submission status: Runtime Error

Solution code:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ALDS1_5_B
{
    class Program
    {
        static long cnt = 0;

        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int[] S = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);

            // rightの初期値は配列の要素数
            MergeSort(S, 0, n);

            Console.WriteLine(cnt);
        }

        static void Merge(int[] A, int left, int mid, int right)
        {
            int n1 = mid - left;
            int n2 = right - mid;
            // 左右それぞれ一つ多く要素を作る
            int[] L = new int[n1 + 1];
            int[] R = new int[n2 + 1];
            // もとの配列を左右に分ける
            for (int i = 0; i < n1; i++)
            {
                L[i] = A[left + i];
            }
            for (int i = 0; i < n2; i++)
            {
                R[i] = A[mid + 1];
            }

            // 無限みたいな
            L[n1] = int.MaxValue;
            R[n2] = int.MaxValue;

            int m = 0, j = 0;
            for (int k = left; k < right; k++)
            {
                if (L[m] <= R[j])
                {
                    A[k] = L[m];
                    m++;

                    cnt += j;
                }
                else
                {
                    A[k] = R[j];
                    j++;
                }
            }
        }


        static void MergeSort(int[] A, int left, int right)
        {
            if (left + 1 < right)
            {
                int mid = (left + right) / 2;
                MergeSort(A, left, mid);
                MergeSort(A, mid, right);
                Merge(A, left, mid, right);
            }
        }

    }
}

Submission status: Runtime Error

Solution code:
MAX = 500000;
maxnum = 1000000010;
cnt=0

def Merge_sort(A):

    def merge(A,left,mid,right):
        global cnt
   
        t1=array.array('L',[])
        t2=array.array('L',[])        
        for i in range(left,mid):
            t1.append(A[i])
        for i in range(mid,right):
            t2.append(A[i])
        t1.append(maxnum)
        t2.append(maxnum)
        
        i=0
        j=0
        k=0
        nl=mid-left
        for k in range(left,right):
            if t1[i]<=t2[j]:
                A[k]=t1[i]
                i+=1
            else:
                A[k]=t2[j]
                j+=1
                cnt+=nl-i

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

    mergesort(A,0,len(A))



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

Submission status: Runtime Error

Solution code:
def shakerSort(A):
	cnt=0
	left=0
	right=len(A)-1
	while left<right:
		for i in range(left,right):
			if A[i]>A[i+1]:
				A[i],A[i+1]=A[i+1],A[i]
				sh=i
				cnt+=1
		right=sh
		for j in range(right,left,-1):
			if A[j]<A[j-1]:
				A[j],A[j-1]=A[j-1],A[j]
				sh=j
				cnt+=1
		left=sh
	return cnt

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

Submission status: Runtime Error

Solution code:
def shakerSort(A):
	cnt=0
	left=0
	right=len(A)-1
	while left<right:
		for i in range(left,right):
			if A[i]>A[i+1]:
				A[i],A[i+1]=A[i+1],A[i]
				sh=i
				cnt+=1
		right=sh
		for j in range(right,left,-1):
			if A[j]<A[j-1]:
				A[j],A[j-1]=A[j-1],A[j]
				sh=j
				cnt+=1
		left=sh
	return cnt

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

Submission status: Runtime Error

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

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

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

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

Submission status: Runtime Error

Solution code:
#coding:utf-8

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

def Merge(A, left, mid, right):
    L = A[left:mid]
    R = A[mid:right]
    L.append(510000)
    R.append(510000)
    i,j = 0,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 += 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)

cnt = 0
MergeSort(A, 0, n)

print(cnt)