def merge_sort(arr):
s = 0
if len(arr) <= 1:
return
mid = len(arr) // 2
l = arr[:mid]
r = arr[mid:]
s += merge_sort(l) + merge_sort(r)
i = j = k = 0
while(i < len(l) and j < len(r)):
if(l[i] <= r[j]):
arr[k] = l[i]
i += 1
k += 1
else:
arr[k] = r[j]
j += 1
k += 1
s += len(l) - i
while(i < len(l)):
arr[k] = l[i]
i += 1
k += 1
while(j < len(r)):
arr[k] = r[j]
j += 1
k += 1
return s
n = int(input())
arr = [int(i) for i in input().split()]
print(merge_sort(arr))
n=int(input())
arr=[0]
arr+=[int(x) for x in input().split()]
ans=0
arr2=[0]*500010
def merge(l,r):#归并排序
global ans
if l==r:
return
mid=int((l+r)/2)
i=l
k=l
j=mid+1
merge(l,mid)
merge(mid+1,r)
while(i<=mid and j<=r):
if(arr[i]<=arr[j]):
arr2[k]=arr[i]
k+=1
i+=1
else:
arr2[k]=arr[j]
k+=1
j+=1
ans+=(mid-i+1)
while(i<=mid):
arr2[k]=arr[i]
k+=1
i+=1
while(j<=r):
arr2[k]=arr[j]
k+=1
j+=1
for m in range(l,r):#复制回原数组
arr[m]=arr2[m]
print(ans)
merge(1,n)
print(arr)
