inv.py

def inv(arr,n):
	if n==1:
		return 0
	else:
		x=inv(arr[0:n/2],n/2)
		y=inv(arr[n/2:n],n/2)
		z=split(arr[0:n/2],arr[n/2:n])
		return x+y+z

def split(a,b):
	a.sort()
	b.sort()
	i=j=k=0
	count=0
	z=[]
	if a[i]<b[j]:
		z.append(a[i])
		k+=1
		i+=1
	else:
		z.append(b[j])
		j+=1
		k+=1
		count+=(len(a)-i)
	return count

if __name__=='__main__':
	arr = [int(line.strip()) for line in open("IntegerArray.txt", 'r')]
	c=inv(arr,len(arr))
	print c