CodeEff/ECCO huggingface dataset:
# Original solution
def merge(A, l, m, r):
  n1 = m - l
  n2 = r - m
  L = [0] * (n1 + 1)
  R = [0] * (n2 + 1)

  for i in range(n1): L[i] = A[l + i]
  for i in range(n2): R[i] = A[m + i]
  L[n1] = float('inf')
  R[n2] = float('inf')

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

def merge_sort(A, l, r):
  count = 0
  if l + 1 < r:
    m = (l + r) // 2
    count += merge_sort(A, l, m)
    count += merge_sort(A, m, r)
    count += merge(A, l, m, r)
  return count

n = int(eval(input()))
A = list(map(int, input().split()))
count = merge_sort(A, 0, len(A))
print((" ".join(map(str, A))))
print(count)

# Optimized solution
def merge(A, l, m, r):
  L = A[l:m] + [SENTINEL]
  R = A[m:r] + [SENTINEL]

  i = 0
  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
  global count
  count += r - l

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

SENTINEL = float('inf')
n = int(eval(input()))
A = list(map(int, input().split()))
count = 0
merge_sort(A, 0, len(A))
print((" ".join(map(str, A))))
print(count)
# Original solution
import sys

def merge(A, left, mid, right, num_compare):
	n1 = mid - left
	n2 = right - mid

	L = [0 for i in range(n1)]
	R = [0 for i in range(n2)]

	for i in range(n1):
		L[i] = A[left + i]

	for i in range(n2):
		R[i] = A[mid + i]
	
	i = 0
	j = 0

	num_compare += right - left
	for k in range(left, right):
		if j >= n2:
			A[k] = L[i]
			i += 1
		elif i < n1 and L[i] <= R[j]:
			A[k] = L[i]
			i += 1
		else:
			A[k] = R[j]
			j += 1
	return num_compare

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

	return num_compare


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



n = int(fin.readline())
S = list(map(int, fin.readline().split()))

num_compare = 0
num_compare = merge_sort(S, 0, n, num_compare)

print(S[0], end = "")
for s in S[1:]:
	print(" " + str(s), end = "")
print("") 
print(num_compare)


# Optimized solution
import sys

def merge(A, left, mid, right, num_compare):
	n1 = mid - left
	n2 = right - mid

	L = A[left:mid] + [SENTINEL]
	R = A[mid:right] + [SENTINEL]

	for i in range(n1):
		L[i] = A[left + i]

	for i in range(n2):
		R[i] = A[mid + i]
	
	i = 0
	j = 0

	num_compare += right - left
	for k in range(left, right):
		if L[i] <= R[j]:
			A[k] = L[i]
			i += 1
		else:
			A[k] = R[j]
			j += 1
	return num_compare

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

	return num_compare


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

SENTINEL = float("inf")

n = int(fin.readline())
S = list(map(int, fin.readline().split()))

num_compare = 0
num_compare = merge_sort(S, 0, n, num_compare)

print(S[0], end = "")
for s in S[1:]:
	print(" " + str(s), end = "")
print("") 
print(num_compare)
# Original solution
import sys

def merge(A, left, mid, right, num_compare):
	n1 = mid - left
	n2 = right - mid

	L = A[left:mid] + [SENTINEL]
	R = A[mid:right] + [SENTINEL]

	for i in range(n1):
		L[i] = A[left + i]

	for i in range(n2):
		R[i] = A[mid + i]
	
	i = 0
	j = 0

	num_compare += right - left
	for k in range(left, right):
		if L[i] <= R[j]:
			A[k] = L[i]
			i += 1
		else:
			A[k] = R[j]
			j += 1
	return num_compare

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

	return num_compare


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

SENTINEL = float("inf")

n = int(fin.readline())
S = list(map(int, fin.readline().split()))

num_compare = 0
num_compare = merge_sort(S, 0, n, num_compare)

print(S[0], end = "")
for s in S[1:]:
	print(" " + str(s), end = "")
print("") 
print(num_compare)


# Optimized solution
import sys

def merge(A, left, mid, right, num_compare):
	n1 = mid - left
	n2 = right - mid

	L = A[left:mid] + [SENTINEL]
	R = A[mid:right] + [SENTINEL]
	
	i = 0
	j = 0

	num_compare += right - left
	for k in range(left, right):
		if L[i] <= R[j]:
			A[k] = L[i]
			i += 1
		else:
			A[k] = R[j]
			j += 1
	return num_compare

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

	return num_compare


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

SENTINEL = float("inf")

n = int(fin.readline())
S = list(map(int, fin.readline().split()))

num_compare = 0
num_compare = merge_sort(S, 0, n, num_compare)

print(S[0], end = "")
for s in S[1:]:
	print(" " + str(s), end = "")
print("") 
print(num_compare)
# Original solution
def merge(A,left,mid,right):
    n1=mid-left
    n2=right-mid
#    L=[0]*(n1+1)
#    R=[0]*(n2+1)
    global L, R
    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
    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

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(input().split())
for i in range(n):
    S[i]=int(S[i])
L=[0]*(n//2+2)
R=[0]*(n//2+2)
cnt=0
mergeSort(S,0,n)
for i in range(n):
    if i==n-1:
        print(S[i])
    else:
        print(S[i],end=" ")
print(cnt)



# Optimized solution
def merge(A,left,mid,right):
    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
    global cnt
    cnt += (right-left)
    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

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(input().split())
for i in range(n):
    S[i]=int(S[i])
cnt=0
mergeSort(S,0,n)
for i in range(n):
    if i==n-1:
        print(S[i])
    else:
        print(S[i],end=" ")
print(cnt)
# Original solution
def merge(A,left,mid,right):
    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
    global cnt
    cnt += (right-left)
    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

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(input().split())
for i in range(n):
    S[i]=int(S[i])
cnt=0
mergeSort(S,0,n)
for i in range(n):
    if i==n-1:
        print(S[i])
    else:
        print(S[i],end=" ")
print(cnt)



# Optimized solution
def merge(A,left,mid,right):
    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
    global cnt
    cnt += (right-left)
    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

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

n=int(input())
S=list(input().split())
for i in range(n):
    S[i]=int(S[i])
cnt=0
mergeSort(S,0,n)
for i in range(n):
    if i==n-1:
        print(S[i])
    else:
        print(S[i],end=" ")
print(cnt)
# Original solution
cnt = 0

def Merge(A, p, q, r):
    n1 = q - p                  # A[p..q-1]の長さ
    n2 = r - q                  # A[q..r-1]の長さ

    # L[0 .. n1] と R[0 .. n2]を作る
    L = []
    for i in range(n1):
        L.append(A[p+i])
    R = []
    for j in range(n2):
        R.append(A[q+j])
    # 配列L, Rの最後に番兵を置く
    L.append(float("inf"))
    R.append(float("inf"))

    i = 0
    j = 0
    global cnt
    for k in range(p, r):
        cnt += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def MergeSort(A, p, r):
    if p + 1 < r:
        q = (p + r)//2
        MergeSort(A, p, q)
        MergeSort(A, q, r)
        Merge(A, p, q, r)



n = int(input())
S = [int(x) for x in input().split()]
MergeSort(S, 0, n)
for i in range(len(S)-1):
    print(S[i], end=" ")
print(S[-1])
print(cnt)


# Optimized solution
cnt = 0

def Merge(A, p, q, r):
    n1 = q - p                  # A[p..q-1]の長さ
    n2 = r - q                  # A[q..r-1]の長さ

    # L[0 .. n1] と R[0 .. n2]を作る
    L = []
    for i in range(n1):
        L.append(A[p+i])
    R = []
    for j in range(n2):
        R.append(A[q+j])
    # 配列L, Rの最後に番兵を置く
    L.append(float("inf"))
    R.append(float("inf"))

    i = 0
    j = 0
    global cnt
    for k in range(p, r):
        cnt += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def MergeSort(A, p, r):
    if p + 1 < r:
        q = (p + r)//2
        MergeSort(A, p, q)
        MergeSort(A, q, r)
        Merge(A, p, q, r)



n = int(eval(input()))
S = [int(x) for x in input().split()]
MergeSort(S, 0, n)
print((' '.join(map(str, S))))
print(cnt)
# Original solution
# -*- coding: utf-8 -*-
"""
Created on Thu May  3 19:22:34 2018
ALDS-1-5-C
@author: maezawa
"""
cnt = 0
n = int(input())
a = list(map(int, input().split()))

def merge_sort(a, left, right):
    #global cnt
    #cnt += 1
    if left+1 < right:
        mid = (left+right)//2
        merge_sort(a, left, mid)
        merge_sort(a, mid, right)
        merge(a, left, mid, right)

def merge(a, left, mid, right):
    global cnt
    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(float('Inf'))
    r.append(float('Inf'))
    i = 0
    j = 0
    
    for k in range(left, right):
        cnt += 1
        if l[i] <= r[j]:
            a[k] = l[i]
            i += 1
        else:
            a[k] = r[j]
            j += 1
            
merge_sort(a, 0, len(a))
print(a[0], end='')
for i in range(1,len(a)):
    print(' {}'.format(a[i]), end='')
print()
print(cnt)
    


# Optimized solution
# -*- coding: utf-8 -*-
"""
Created on Thu May  3 19:22:34 2018
ALDS-1-5-C
@author: maezawa
"""
cnt = 0
n = int(input())
a = list(map(int, input().split()))

def merge_sort(a, left, right):
    #global cnt
    #cnt += 1
    if left+1 < right:
        mid = (left+right)//2
        merge_sort(a, left, mid)
        merge_sort(a, mid, right)
        merge(a, left, mid, right)

def merge(a, left, mid, right):
    global cnt
    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(10**10)
    r.append(10**10)
    i = 0
    j = 0
    
    for k in range(left, right):
        cnt += 1
        if l[i] <= r[j]:
            a[k] = l[i]
            i += 1
        else:
            a[k] = r[j]
            j += 1
            
merge_sort(a, 0, len(a))
print(a[0], end='')
for i in range(1,len(a)):
    print(' {}'.format(a[i]), end='')
print()
print(cnt)
# Original solution
#ALDS1_5-B Merge Sort
from collections import deque

def merge(A,B):
    ans = deque()
    count = 0
    while(True):
        if len(A)==0 and len(B) == 0:
            break
        elif len(A) == 0:
            ans.append(B.popleft())
        elif len(B) == 0:
            ans.append(A.popleft())
        elif A[0] > B[0]:
            ans.append(B.popleft())
        else:
            ans.append(A.popleft())
        count+=1
    return (ans,count)

n = int(eval(input()))
S = [int(i) for i in input().split()]
div = deque([S])
mer = deque()
count = 0
while(len(div)>0):
    d = div.pop()
    if(len(d)>2):
        mid = len(d)//2
        div.appendleft(d[:mid])
        div.appendleft(d[mid:])
    elif(len(d)==2):
        if d[0] > d[1]:
            mer.appendleft(d[::-1])
        else:
            mer.appendleft(d)
        count+=2
    else:
        mer.appendleft(d)
        
while(len(mer)>1):
    A = deque(mer.popleft())
    B = deque(mer.popleft())
    ret = merge(A,B)
    mer.append(ret[0])
    count+=ret[1]
    
ans = ""
for i in ret[0]:
    ans += str(i) + " "
print((ans[:-1]))
print(count)


# Optimized solution
#ALDS1_5-B Merge Sort
from collections import deque

def merge(A,B):
    ans = deque()
    count = 0
    while(True):
        if len(A)==0:
            if len(B)==0:
                break
            ans.append(B.popleft())
        elif len(B) == 0:
            ans.append(A.popleft())
        elif A[0] > B[0]:
            ans.append(B.popleft())
        else:
            ans.append(A.popleft())
        count+=1
    return (ans.copy(),count)

n = int(eval(input()))
S = [int(i) for i in input().split()]
div = deque([S])
mer = deque()
count = 0
while(len(div)>0):
    d = div.pop()
    if(len(d)>2):
        mid = len(d)//2
        div.appendleft(d[:mid])
        div.appendleft(d[mid:])
    elif(len(d)==2):
        if d[0] > d[1]:
            mer.appendleft(d[::-1])
        else:
            mer.appendleft(d)
        count+=2
    else:
        mer.appendleft(d)
        
while(len(mer)>1):
    A = deque(mer.popleft())
    B = deque(mer.popleft())
    ret = merge(A,B)
    mer.append(ret[0])
    count+=ret[1]
    
ans = ""
for i in ret[0]:
    ans += str(i) + " "
print((ans[:-1]))
print(count)
# Original solution
def mergeSort(A, left, right, n):
    if left + 1 < right:
        mid = int((right + left ) / 2 )
        mergeSort(A, left, mid, n)
        mergeSort(A, mid, right, n)
        return (merge(A, left, mid, right, n))

def merge(A, left, mid, right, n):
    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 = j = 0
    for k in range(left, right):
        A[n] += 1
        if L[i] <= R[j]:
            key = L[i]
            A[k] = key
            i += 1
        else:
            key = R[j]
            A[k] = key
            j += 1
    return A

n = int(input())
A = list(map(int, input().split()))
A.append(0)
S = mergeSort(A, 0, len(A) - 1, n)
for i in range(n - 1):
    print(S[i], end = ' ')
print(S[n - 1])
print(S[n])


# Optimized solution
def mergeSort(A, left, right, n):
    if left + 1 < right:
        mid = int((right + left ) / 2 )
        mergeSort(A, left, mid, n)
        mergeSort(A, mid, right, n)
        return (merge(A, left, mid, right, n))

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

n = int(eval(input()))
A = list(map(int, input().split()))
A.append(0)
S = mergeSort(A, 0, len(A) - 1, n)
print((" ".join(list(map(str, S[:n])))))
print((S[n]))
# Original solution
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
    lcount = 0
    rcount = 0
    merged = []
    while lpos < len(left) and rpos < len(right):
        if left[lpos] <= right[rpos]:
            merged.append(left[lpos])
            lpos += 1
            lcount += 1
        else:
            merged.append(right[rpos])
            rpos += 1
            rcount += 1
    
    if left[lpos:]:
        merged.extend(left[lpos:])
        lcount += len(left[lpos:])
    if right[rpos:]:
        merged.extend(right[rpos:])
        rcount += len(right[rpos:])
        
    return merged, lcount + rcount

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

# Optimized solution
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
    #lcount = 0
    #rcount = 0
    merged = []
    while lpos < len(left) and rpos < len(right):
        if left[lpos] <= right[rpos]:
            merged.append(left[lpos])
            lpos += 1
            #lcount += 1
        else:
            merged.append(right[rpos])
            rpos += 1
            #rcount += 1
    
    if left[lpos:]:
        merged.extend(left[lpos:])
        #lcount += len(left[lpos:])
    if right[rpos:]:
        merged.extend(right[rpos:])
        #rcount += len(right[rpos:])
    
    #print merged
    #return merged, lcount + rcount
    return merged, len(merged)

if __name__ == '__main__':
    n = int(input())
    A = list(map(int, input().split()))
    
    sorted, count = merge_sort(A)
    print(' '.join(str(x) for x in sorted))
    print(count)
# Original solution
n = int(input())
S = list(map(int, input().split()))
cnt = 0

def merge(A, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    L = [0] * (n1+1) 
    R = [0] * (n2+1)
    #L[:n1] = A[left:mid]
    #R[:n2] = A[mid:right]
    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
            cnt += 1
        else:
            A[k] = R[j]
            j += 1
            cnt += 1
    return 0

def mergeSort(A, left, right):
    if right - left > 1:
        mid = int((left + right) / 2)
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
    return 0

def main():
    mergeSort(S, 0, len(S))
    print(' '.join(map(str, S)))
    print(cnt)
    return 0

main()

# Optimized solution
n = int(input())
S = list(map(int, input().split()))
cnt = 0

def merge(A, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    L = [0] * (n1+1) 
    R = [0] * (n2+1)
    L[:n1] = A[left:mid]
    R[:n2] = A[mid:right]
    #for i in xrange(n1):
    #    L[i] = A[left + i]
    #for i in xrange(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
            cnt += 1
        else:
            A[k] = R[j]
            j += 1
            cnt += 1
    return 0

def mergeSort(A, left, right):
    if right - left > 1:
        mid = int((left + right) / 2)
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
    return 0

def main():
    mergeSort(S, 0, len(S))
    print(' '.join(map(str, S)))
    print(cnt)
    return 0

main()
# Original solution
cnt = 0

def merge(A, l, m, r):
    n1, n2 = m - l, r - m
    L = [A[l + i] for i in range(n1)]
    R = [A[m + i] for i in range(n2)]
    L.append(10 ** 10)
    R.append(10 ** 10)
    i, j = 0, 0
    global cnt
    for k in range(l, r):
        cnt += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def mergeSort(A, l, r):
    if r - l > 1:
        m = (l + r) // 2
        mergeSort(A, l, m)
        mergeSort(A, m, r)
        merge(A, l, m, r)

n = int(eval(input()))
A = list(map(int, input().split()))
mergeSort(A, 0, n)
print((" ".join(list(map(str, A)))))
print(cnt)

# Optimized solution
def merge(A, l, m, r):
    n1, n2 = m - l, r - m
    L = [A[l + i] for i in range(n1)] + [10 ** 10]
    R = [A[m + i] for i in range(n2)] + [10 ** 10]
    i, j = 0, 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
    global cnt
    cnt += r - l

def mergeSort(A, l, r):
    if r - l > 1:
        m = (l + r) // 2
        mergeSort(A, l, m)
        mergeSort(A, m, r)
        merge(A, l, m, r)

n = int(eval(input()))
A = list(map(int, input().split()))
cnt = 0
mergeSort(A, 0, n)
print((" ".join(list(map(str, A)))))
print(cnt)
# Original solution
def merge_jibun(A, left, mid, right):
    L = A[left:mid] + [1000000]
    R = A[mid:right] + [1000000]
    # L.append(1000000)
    # R.append(1000000)

    i = 0
    j = 0
    global count
    
    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

def merge_hoka(A, left, mid, right):
    global count
    inf = 10 ** 9
    L = A[left:mid] + [inf]
    R = A[mid:right] + [inf]
 
    i = 0
    j = 0
    for k in range(left, right):
        count += 1
        # print(L)
        # print(R)
        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_jibun(A, left, mid, right)
        merge_hoka(A, left, mid, right)

n = int(eval(input()))
A = list(map(int, input().split()))
count = 0
mergeSort(A, 0, n)

print((' '.join(list(map(str, A)))))
print(count)


# Optimized solution
def merge_jibun(A, left, mid, right):
    global count
    inf = 10 ** 9
    L = A[left:mid] + [inf]
    R = A[mid:right] + [inf]
    # L.append(1000000)
    # R.append(1000000)

    i = 0
    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

def merge_hoka(A, left, mid, right):
    global count
    inf = 10 ** 9
    L = A[left:mid] + [inf]
    R = A[mid:right] + [inf]
 
    i = 0
    j = 0
    for k in range(left, right):
        count += 1
        # print(L)
        # print(R)
        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_jibun(A, left, mid, right)
        # merge_hoka(A, left, mid, right)

n = int(eval(input()))
A = list(map(int, input().split()))
count = 0
mergeSort(A, 0, n)

print((' '.join(list(map(str, A)))))
print(count)