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: Wrong Answer

Solution code:
n = int(input())
A = [(i,int(j)) for i,j in enumerate(input().split())]
A = sorted(A, key=lambda x: x[1])
ans=0
for i,j in enumerate(A):
    ans+=abs(i-j[0])
print(ans-n+1)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left


def count_inversion(A):
    cnt = 0
    for i in reversed(range(len(A) - 1)):
        j = bisect_left(A, A[i], i + 1, len(A))
        cnt += j - i - 1
        tmp = A[i]
        A[i:j - 2] = A[i + 1:j - 1]
        A[j - 1] = tmp
    return cnt


def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    print(count_inversion(A))


main()

Submission status: Wrong Answer

Solution code:
#! /usr/local/bin/python3
# coding: utf-8

from sys import stdin

cnt = 0


def swap(A, i, j):
    global cnt

    cnt += j - i
    tmp = A[i]
    A[i] = A[j]
    A[j] = tmp
    #print(*A, i, j)


def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            swap(A, i, j)
    swap(A, i + 1, r)
    return i + 1


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


def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    count_inversion(A, 0, n - 1)
    print(cnt)


main()

Submission status: Wrong Answer

Solution code:
#! /usr/local/bin/python3
# coding: utf-8

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(*A)
    print(inv)


main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from 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(int(c+1))

Submission status: Wrong Answer

Solution code:
from 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
c += 1    
print(c)

Submission status: Wrong Answer

Solution code:
c = 0
def m(L,R):   
    global c
    j = 0
    for l in L:
        while (j < len(R) and R[j] < l):
            yield R[j]
            j += 1
        yield l
    while (j < len(R)):
        yield R[j]
        j += 1
    c += len(L) + len(R)
    
def merge(A):
    global c
    if len(A) == 1:
        return A
    if len(A) == 2:
        c += 2
        a, b = A
        return A if a < b else (b, a)
    mid = len(A)//2
    A[:] = m(merge(A[:mid]), merge(A[mid:]))
    return A
    
n = int(input())
nlist = list(map(int,input().split()))
A = merge(nlist)  
print(c)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
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
            #print(l_fore,l_rear, array[:23])
            #print(num_of_inversions,len(l_fore),len(l_rear),i,j,k)
            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(" ".join(map(str, array[:n])))
    print(num_of_inversions)

    return


main()

Submission status: Wrong Answer

Solution code:
#marge sort マージソート ＋　転倒数

a = [3,5,2,1,4]
cnt = 0

def marge(A, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    L = [0]*(n1+1) 
    R = [0]*(n2+1)
    #L[0,,,,,n1]とr[0,,,,n2]を生成
    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)

Submission status: Wrong Answer

Solution code:
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) - j - 1
            j += 1

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

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

Submission status: Wrong Answer

Solution code:
import bisect, sys
n = sys.stdin.readline()
cnt = 0
a = []
for ai in map(int, sys.stdin.readline().split()):
    pos = bisect.bisect_left(a, ai)
    a.insert(pos, ai)
    cnt += len(a) - pos

print(cnt)

Submission status: Wrong Answer

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

print(lambda s: sum(a > b for i, b in enumerate(s) for a in s[:i]))

Submission status: Wrong Answer

Solution code:
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
    for k in xrange(left, right):
        count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            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/2

Submission status: Wrong Answer

Solution code:
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, 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 += 1


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(num)
print(cnt - 1)

Submission status: Wrong Answer

Solution code:
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, 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 += 1


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

Submission status: Wrong Answer

Solution code:
def merge_sort(A):
    if len(A) <= 1:
        return A, 0
    mid = len(A) // 2
    #print A[:mid]
    #print A[mid:]
    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 = []
    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
    org = []
    org.extend(left)
    org.extend(right)
    return org, rcount

if __name__ == '__main__':
    n = int(raw_input())
    A = map(long, raw_input().split())
    
    sorted, count = merge_sort(A)
    #print ' '.join(str(x) for x in sorted)
    print count

Submission status: Wrong Answer

Solution code:
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
            cnt += n1 - i + 1
        else:
            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)

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    S = map(int, lines[1].split())
    mergeSort(S, 0, int(lines[0]))
    print cnt

Submission status: Wrong Answer

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

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):
        count += 1
        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

Submission status: Wrong Answer

Solution code:
def merge(a, left, mid, right):
    global cnt
    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:
            cnt += 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(input())
a = list(map(int, input().split()))
cnt = 0
mergesort(a, 0, n)
print(cnt-1)

Submission status: Wrong Answer

Solution code:
import sys

sintinel = 1000000001

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

def merge(A, l, mid, r):
    global count
    L = A[l:mid] + [sintinel]
    R = A[mid:r] + [sintinel]
    i = 0
    j = 0
    for k in range(l, r):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            count += 1
            A[k] = R[j]
            j += 1

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

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

Submission status: Wrong Answer

Solution code:
def bubble_sort_revision(target_list):

    list_length = len(target_list)
    
    flag = True
    change_count = 0
    top_index = 1
    while flag:
        flag = False
        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
                flag = True
        top_index += 1
        print(target_list)
    print(target_list)
    return change_count
if __name__ == "__main__":
    l = input()
    target_list = [int(i) for i in input().split()]
    print(bubble_sort_revision(target_list))

Submission status: Wrong Answer

Solution code:
def bubble_sort_revision(target_list):

    list_length = len(target_list)
    
    flag = True
    change_count = 0
    top_index = 1
    while flag:
        flag = False
        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
                flag = True
        top_index += 1

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

Submission status: Wrong Answer

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-1):
        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
        print(target_list)
    print(target_list)
    return change_count
if __name__ == "__main__":
    l = input()
    target_list = [int(i) for i in input().split()]
    print(bubble_sort_revision(target_list))

Submission status: Wrong Answer

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-1):
        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
if __name__ == "__main__":
    l = input()
    target_list = [int(i) for i in input().split()]
    print(bubble_sort_revision(target_list))

Submission status: Wrong Answer

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
    print(target_list)
    return change_count
if __name__ == "__main__":
    l = input()
    target_list = [int(i) for i in input().split()]
    print(bubble_sort_revision(target_list))

Submission status: Wrong Answer

Solution code:

def merge(ns, ns1, ns2, n, mid):
    j = 0
    k = 0
    c = 0
    for i in range(n):
        if ns1[j] < ns2[k]:
            ns[i] = ns1[j]
            j += 1
            if j == mid:
                for l in range(n - mid - k):
                    ns[i + 1 + l] = ns2[k + l]
                    return c
        else:
            ns[i] = ns2[k]
            k += 1
            c += mid - j
            if k == n - mid:
                for l in range(mid - j):
                    ns[i + 1 + l] = ns1[j + l]
                    return c

def merge_sort(ns, n):
    if n <= 1:
        return 0
    elif n == 2:
        if ns[0] > ns[1]:
            k = ns[0]
            ns[0] = ns[1]
            ns[1] = k
            return 1
        else:
            return 0
    else:
        mid = n // 2
        ns1 = ns[:mid]
        ns2 = ns[mid:]
        c1 = merge_sort(ns1, mid)
        c2 = merge_sort(ns2, n - mid)
        c3 = merge(ns, ns1, ns2, n, mid)
        return c1 + c2 + c3

def compute_inversions(ns, n):
    return merge_sort(ns, n)

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

print(compute_inversions(ns, n))

Submission status: Wrong Answer

Solution code:
import sys

a_max = 10000000000

def merge_sort(A):
	n = len(A)
	num_swap = 0

	if n > 1:
		m = n // 2
		num_swap0, A0 = merge_sort(A[0:m])
		num_swap1, A1 = merge_sort(A[m:])
		
		num_swap += num_swap0 + num_swap1

		n1 = len(A0)
		A0.append(a_max)
		A1.append(a_max)	
		i = 0
		j = 0		
		
		for k in range(n):
			if A0[i] < A1[j]:
				A[k] = A0[i]

				i += 1
			else:
				A[k] = A1[j]

				num_swap += n1 - i
				j += 1

	return num_swap, A

def bubble_sort(A):
	n = len(A)
	num_swap = 0

	for i in range(n):
		for j in range(n - 1, i, -1):
			if A[j] < A[j - 1]:
				A[j], A[j - 1] = A[j - 1], A[j]
				num_swap += 1

	return num_swap, A

#fin = open("test.txt", "r")
fin = sys.stdin

fin.readline()
A = list(map(int, fin.readline().split()))

num_swap, B = merge_sort(A)
#num_swap, B = bubble_sort(A)

print(num_swap)
print(B)

Submission status: Wrong Answer

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):
        cnt += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i+1
        
        else:
            A[k] = R[j]
            j = j+1
    return cnt

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: Wrong Answer

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
            cnt += 1
        
        else:
            A[k] = R[j]
            j = j+1
    return cnt

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: Wrong Answer

Solution code:
def merge(A, left, mid, right):
    global count
    # count += (right - left)
    L = A[left:mid] + [int(1e9)]
    R = A[mid:right] + [int(1e9)]
    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 += 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)

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

Submission status: Wrong Answer

Solution code:
def merge(A, left, mid, right):
    global count
    # count += (right - left)
    L = A[left:mid] + [int(1e9)]
    R = A[mid:right] + [int(1e9)]
    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 += j

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
count = 0

def countInverse(a, i):
    if i == n:
        return
    elif a[i] < a[i + 1]:
        count += 1
    countInverse(a, i + 1)

print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = list(map(int,input().split()))
count = 0

def merge(a, left, mid, right):
    global count
    l = a[left:mid] + [float("inf")]
    r = a[mid:right] + [float("inf")]
    i = j = 0
    for k in range(left, right):
        if l[i] <= r[j]:
            a[k] = l[i]
            i += 1
        else:
            a[k] = r[j]
            j += 1
            count += 1

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

mergeSort(s, 0, n)

print(count - 1)

Submission status: Wrong Answer

Solution code:

cnt = 0
def merge(A,left,mid,right):
    '''n1 = mid - left
    n2 = right - mid
    L = []
    R = []
    for i in range(0,n1):
        L.append(A[left+i])
 
    for i in range(0,n2):
        R.append(A[mid+i])
    L.append(1000000001)
    R.append(1000000001)
    '''
    L = A[left:mid]+[1000000001]
    R = A[mid:right]+[1000000001]
 
    i = 0
    j = 0
    global cnt
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k]=L[i]
            i += 1
        else:
            cnt += 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)
 
 
if __name__ == '__main__':
    n = (int)(input())
    a = list(map(int,input().split()))
     
    mergeSort(a,0,n)
#    print(*a)
    print(cnt-1)

Submission status: Wrong Answer

Solution code:
def merge(A, left, mid, right):
	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(1000000001)
	R.append(1000000001)
	i = 0
	j = 0
	for k in xrange(left, right):
		global cnt
		if L[i] <= R[j]:
			A[k] = L[i]
			i += 1
		else:
			A[k] = R[j]
			j += 1
			cnt += 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)
	return A

n = int(raw_input())
S = map(int, raw_input().split())

cnt = 0
mergeSort(S, 0, n)

print cnt

Submission status: Wrong Answer

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

def merge_and_count(a, b):
    i, j = 0, 0
    count = 0
    m = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            m.append(a[i])
            i += 1
        else:
            count += len(a)-i
            m.append(b[j])
            j += 1

    if i < len(a):
        m += a[i:]
    else:
        m += b[j:]

    return (count, m)



def sort_and_count(l):
    if len(l) == 1:
        return 0, []
    else:
        a = l[0:len(l)//2]
        b = l[len(l)//2:]
        rA, a_ = sort_and_count(a)
        rB, b_ = sort_and_count(b)
        r, l_ = merge_and_count(a, b)
#        print(a, b)
#        print(rA, rB, a_, b_, r, l_)
    return (rA+rB+r, l_)

print(sort_and_count(a)[0])

Submission status: Wrong Answer

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

def merge_and_count(a, b):
    i, j = 0, 0
    count = 0
    m = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            m.append(a[i])
            i += 1
        else:
            count += len(a)-i
            m.append(b[j])
            j += 1

    if i < len(a):
        m += a[i:]
    else:
        m += b[j:]

    return (count, m)



def sort_and_count(l):
    if len(l) == 1:
        return 0, []
    else:
        a = l[0:len(l)//2]
        b = l[len(l)//2:]
        rA, a_ = sort_and_count(a)
        rB, b_ = sort_and_count(b)
        r, l_ = merge_and_count(a, b)
#        print(a, b)
#        print(rA, rB, a_, b_, r, l_)
    return (rA+rB+r, l_)

print(sort_and_count(a)[0])

Submission status: Wrong Answer

Solution code:
INF = float("inf")
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:
            cnt += 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(input())
S = list(map(int, input().split()))
mergeSort(S, 0, n)
print(cnt - 1)

Submission status: Wrong Answer

Solution code:
INF = float("inf")
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]
            cnt += j
            i += 1
        else:
            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(input())
S = list(map(int, input().split()))
mergeSort(S, 0, n)
print(*S)
print(cnt)

Submission status: Wrong Answer

Solution code:
def m(L,R):
 T=[];global c
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()];c-=1
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=-int(input())-2
print(*d(list(map(int,input().split()))))
print(c)

Submission status: Wrong Answer

Solution code:
def m(L,R):
 T=[];global c
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()];c-=1
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=-int(input())-2
d(list(map(int,input().split())))
print(c)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# Merge Sortを元に分割統治で反転数を求める
cnt = -1 # 反転数 Lの最後の要素は必ず無限大であり，反転とカウントされてしまうので1減らしておく
def merge(A, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    L = [A[i] for i in range(left, mid)]
    R = [A[i] for i in range(mid, right)]
    L.append(float("inf"))
    R.append(float("inf"))
    i = j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            cnt += 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)

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