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:
# 16D8101012J ItoJun dj Python3
count=0
def merge(A, left, mid, right):
    global count
    L=A[left:mid]+[2**32]
    R=A[mid:right]+[2**32]
    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+=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().split()))
    merge_sort(A,0,n)
    print(*A)
    print(count)

Submission status: Wrong Answer

Solution code:
# 16D8101012J ItoJun dj Python3
count=0
def merge(A, left, mid, right):
    global count
    L=A[left:mid]+[2**32]
    R=A[mid:right]+[2**32]
    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+=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().split()))
    merge_sort(A,0,n)
    print(*A)
    print(count)

Submission status: Wrong Answer

Solution code:
# 16D8101012J ItoJun dj Python3
count=0
def merge(A, left, mid, right):
    global count
    L=A[left:mid]+[2**32]
    R=A[mid:right]+[2**32]
    i=0
    j=0
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
            count+=1
        else:
            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) 

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

Submission status: Wrong Answer

Solution code:
# 16D8101012J ItoJun dj Python3
count=0
def merge(A, left, mid, right):
    global count
    L=A[left:mid]+[2**32]
    R=A[mid:right]+[2**32]
    i=0
    j=0
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
            count+=1
        else:
            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) 

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

Submission status: Wrong Answer

Solution code:
# 16D8101012J ItoJun dj Python3
count=0
def merge(A, left, mid, right):
    global count
    L=A[left:mid]+[2**32]
    R=A[mid:right]+[2**32]
    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+=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().split()))
    merge_sort(A,0,n)
    print(count)

Submission status: Wrong Answer

Solution code:
# 16D8101012J ItoJun dj Python3
count=0
def merge(A, left, mid, right):
    global count
    L=A[left:mid]+[2**32]
    R=A[mid:right]+[2**32]
    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+=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().split()))
    merge_sort(A,0,n)
    print(count)

Submission status: Wrong Answer

Solution code:
# 16D8101012J ItoJun dj Python3
count=0
def merge(A, left, mid, right):
    global count
    L=A[left:mid]+[2**32]
    R=A[mid:right]+[2**32]
    i=0
    j=0
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
            count+=1
        else:
            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) 

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

Submission status: Wrong Answer

Solution code:
count=0
def merge(A, left, mid, right):
    global count
    L=A[left:mid]+[2**32]
    R=A[mid:right]+[2**32]
    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+=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().split()))
    merge_sort(A,0,n)
    print(count-1)

Submission status: Wrong Answer

Solution code:
# 16D8101012J ItoJun dj Python3
count=0
def merge(A, left, mid, right):
    global count
    h=[]
    L=A[left:mid]+[2**32]
    R=A[mid:right]+[2**32]
    i=0
    j=0
    for k in range(left,right):
        if L[i] <= R[j]:
            print("{}<={}".format(L[i],R[j]))
            A[k] = L[i]
            h.append(L[i])
            i += 1
        else:
            print("{}>{}".format(L[i],R[j]))
            A[k] = R[j]
            h.append(R[j])
            j += 1
            if i < len(L)-1:
                count += len(L) - 1 - i
        
def merge_sort(A, left, right):
    if left+1 < right:
        mid=(left+right)//2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)

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

Submission status: Wrong Answer

Solution code:
def combSort(A):
	cnt=0
	h=len(A)
	while h>1:
		h=(int)(h/1.3)
		for i in range(n-h):
			if A[i]>A[i+h]:
				A[i],A[i+h]=A[i+h],A[i]
				cnt+=1
		print(A)
		
	return cnt

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

Submission status: Wrong Answer

Solution code:
#16D8103010K Ko Okasaki
#ALDS_5_D

global cnt
cnt=0

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

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

mergeSort(S,0,n)
print(*S)
print(cnt)

Submission status: Wrong Answer

Solution code:
global cnt
cnt=0

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

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

mergeSort(S,0,n)
print(*S)
print(cnt)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
def merge(a, left, mid, right):
    INF = int(1e+11)
    l = a[left:mid]
    r = a[mid:right]
    l.append(INF)
    r.append(INF)
    i = 0
    j = 0

    ans = 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 += 1

    return ans


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

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

print(merge_sort(a, 0, len(a)) - 1)

Submission status: Wrong Answer

Solution code:
def merge(a, left, mid, right):
    INF = int(1e+11)
    l = a[left:mid]
    r = a[mid:right]
    l.append(INF)
    r.append(INF)
    i = 0
    j = 0

    ans = 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
            if l[i] != INF:
                ans += 1

    return ans


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

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

print(merge_sort(a, 0, len(a)))

Submission status: Time Limit Exceeded

Solution code:
import sys
cnt2 = 0

def bubble_sort(a):
	cnt = 0
	n = len(a)
	for i in range(n):
		for j in range(n-1, i, -1):
			if a[j] < a[j-1]:
				tmp = a[j]
				a[j] = a[j-1]
				a[j-1] = tmp
				cnt += 1
	return cnt

def merge_sort(a):
	merge_sort_(a, 0, len(a))

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

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

def inversion(a):
	cnt = 0
	for i in range(n):
		for j in range(i+1, n):
			if a[i] > a[j]:
				cnt += 1
	return cnt
	
n = int(input())
a1 = list(map(int, input().split()))
a2 = [0] * n
for i in range(n):
	a2[i] = a1[i]

#cnt1 = bubble_sort(a1)
#print(a1)
#print(cnt1)
cnt2 = inversion(a2)
#print(a2)
print(cnt2)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def swap(A, i, j):
    tmp = A[i]
    A[i] = A[j]
    A[j] = tmp


def count_inversion(A):
    cnt = 0
    for i in range(len(A)):
        for j in reversed(range(i + 1, len(A))):
            if A[j] < A[j - 1]:
                swap(A, j, j - 1)
                cnt += 1
    # print(A)
    return cnt


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


main()

Submission status: Time Limit Exceeded

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]
        del A[i]
        A.insert(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: Time Limit Exceeded

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 - 1] = A[i + 1:j]
        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: Time Limit Exceeded

Solution code:
from bisect import bisect_left


def count_inversion(A):
    cnt = 0
    L = len(A)
    for i in reversed(range(L - 1)):
        j = bisect_left(A, A[i], i + 1, L)
        cnt += j - i - 1
        tmp = A[i]
        del A[i]
        A.insert(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: Time Limit Exceeded

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(max(A))
ans = 0
for j in range(N):
    ans += j - BIT.sum(A[j])
    BIT.add(A[j], 1)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
nd = list(map(int, input().split()))
c = 0
for i in range(n):
    m = min(nd)
    index = nd.index(m)
    nd.remove(m)
    c += index
print(c)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
def inv_number(A):
    cnt = 0
    left = []
    for i, a in enumerate(A):
        j = bisect_right(left, a)
        cnt += i - j
        left.insert(j, a)
    return cnt
n = int(input())
print(inv_number(list(map(int, input().split()))))

Submission status: Time Limit Exceeded

Solution code:
def main():
    input()
    array = [int(x) for x in input().split()]
    counting_dict = {}
    for val in array:
        if val not in counting_dict:
            counting_dict[val] = [1, 0]
        count = 0
        for key in counting_dict.keys():
            if key > val:
                count += counting_dict[key][0]
        counting_dict[val][1] += count

    swaps = 0
    for value in counting_dict.values():
        swaps += value[1]
    print(swaps)

    return

main()

Submission status: Time Limit Exceeded

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

    return sequence_len, sequence

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

def PrintOut(cnt):
    print(cnt)

def main():
    [sequence_len, sequence] = InputData()
    cnt = bubbleSort(sequence)
    PrintOut(cnt)

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def bubble_sort(a):
    cnt = 0
    for i in range(len(a)):
        for j in range(len(a) - 1, i, -1):
            if a[j] < a[j-1]:
                a[j], a[j - 1] = a[j - 1], a[j]
                cnt += 1
    return cnt

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

Submission status: Time Limit Exceeded

Solution code:
def bubble_sort_cnt(a):
    cnt = 0
    for i in range(len(a) - 1):
        for j in range(i + 1, len(a)):
            if a[i] > a[j]:
                cnt += 1
    return cnt

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

Submission status: Time Limit Exceeded

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)
    cnt += len(a) - pos
    a.insert(pos, ai)
 
print(cnt)

Submission status: Time Limit Exceeded

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)
    cnt -= pos
    a.insert(pos, ai)

print(((len(a) - 1) * len(a)) // 2 + cnt)

Submission status: Time Limit Exceeded

Solution code:
n = input()
a = list(map(int, input().split()))
cnt = 0
for i, j in enumerate(a):
    for j2 in a[i:]:
        if j > j2:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import itertools

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

for item in itertools.combinations(numbers, 2):
    if item[0] > item[1]:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
def num_of_inversions(A, n):
    """Print the number of inversions in the sequence A.

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

    cnt = 0
    for i in range(n - 1):
        flag = 0
        for j in range(n - 1, i, -1):
            if A[j] < A[j - 1]:
                A[j], A[j - 1] = A[j - 1], A[j]
                cnt += 1
                flag = 1
        if flag == 0:
            break
    print(cnt)


import sys

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

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

num_of_inversions(A, n)

Submission status: Time Limit Exceeded

Solution code:
def num_of_inversions(A, left, right):
    """Return the number of inversions in the sequence A.
    Using Recursion/Divide and Conquer algorithm.

    A is a list of integers.
    left is the starting index, initially 0.
    right is the value added 1 to the last index, initially the length of A.
    """

    global cnt
    if left + 1 < right:
        mid = (left + right) // 2
        L = A[left:mid]
        R = A[mid:right]
        for r in R:
            for l in L:
                if r < l:
                    cnt += 1
        num_of_inversions(A, left, mid)
        num_of_inversions(A, mid, right)


import sys

cnt = 0

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

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

num_of_inversions(A, 0, n)

print(cnt)

Submission status: Time Limit Exceeded

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

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: Time Limit Exceeded

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
    
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: Time Limit Exceeded

Solution code:
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 = []
    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 = map(int, raw_input().split())
    
    sorted, count = merge_sort(A)
    #print ' '.join(str(x) for x in sorted)
    print count

Submission status: Time Limit Exceeded

Solution code:
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 = []
    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 = map(int, raw_input().split())
    
    sorted, count = merge_sort(A)
    #print ' '.join(str(x) for x in sorted)
    print count

Submission status: Time Limit Exceeded

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('I', [])
    len_left = len(left)
    len_right = len(right)
    while lpos < len_left and rpos < len_right:
        if left[lpos] < right[rpos]:
            merged.append(left[lpos])
            lpos += 1
        else:
            merged.append(right[rpos])
            rpos += 1
            rcount += len(left[lpos:])
    
    if left[lpos:]:
        merged.extend(left[lpos:])
    if right[rpos:]:
        merged.extend(right[rpos:])
    
    return merged, rcount
    
if __name__ == '__main__':
    n = int(raw_input())
    A = array.array('I', map(int, raw_input().split()))
    
    sorted, count = merge_sort(A)
    #print ' '.join(str(x) for x in sorted)
    print count

Submission status: Time Limit Exceeded

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('L', [])
    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('L', map(int, raw_input().split()))
    
    sorted, count = merge_sort(A)
    #print ' '.join(str(x) for x in sorted)
    print count

Submission status: Time Limit Exceeded

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('i', [])  # 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('i', map(int, raw_input().split()))
    
    sorted, count = merge_sort(A)
    #print ' '.join(str(x) for x in sorted)
    print count

Submission status: Time Limit Exceeded

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('l', [])  # 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('l', map(int, raw_input().split()))
    
    sorted, count = merge_sort(A)
    #print ' '.join(str(x) for x in sorted)
    print count

Submission status: Time Limit Exceeded

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('I', [])  # 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('I', map(int, raw_input().split()))
    
    sorted, count = merge_sort(A)
    #print ' '.join(str(x) for x in sorted)
    print count

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(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: Time Limit Exceeded

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: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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