#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
?????????????????????Merge Sort??????????????±??????????????\??????????????¢?????´???????????§???
?¬?????????????????£????????????¨?????§????????????

merge(A, left, mid, right)
  n1 = mid - left;
  n2 = right - mid;
  L[0...n1], R[0...n2] ?????????
  for i = 0 to n1-1
    L[i] = A[left + i]
  for i = 0 to n2-1
    R[i] = A[mid + i]
  L[n1] = INFTY
  R[n2] = INFTY
  i = 0
  j = 0
  for k = left to right-1
    if L[i] <= R[j]
      A[k] = L[i]
      i = i + 1
    else 
      A[k] = R[j]
      j = j + 1

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 ????????´??°???????????°??? S ????????????????????????????????£???????????????????????§
???????????´?????????????????°????????????????????????????????????
?????????merge???????????????????????°????????°?????±????????????????????????
"""

MAX = 100000000

def merge(A, left, mid, right, cnt):
#    print("l:{} m:{} r:{} cnt:{}".format(left,mid,right,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(MAX)
    R.append(MAX)

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

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

def main():
    """ ????????? """
    n = int(input())
    S = list(map(int,input().split()))
    cnt = mergeSort(S, 0, n, 0)
    print(" ".join(map(str,S)))
    print(cnt)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
?????????????????????Merge Sort??????????????±??????????????\??????????????¢?????´???????????§???
?¬?????????????????£????????????¨?????§????????????

merge(A, left, mid, right)
  n1 = mid - left;
  n2 = right - mid;
  L[0...n1], R[0...n2] ?????????
  for i = 0 to n1-1
    L[i] = A[left + i]
  for i = 0 to n2-1
    R[i] = A[mid + i]
  L[n1] = INFTY
  R[n2] = INFTY
  i = 0
  j = 0
  for k = left to right-1
    if L[i] <= R[j]
      A[k] = L[i]
      i = i + 1
    else 
      A[k] = R[j]
      j = j + 1

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 ????????´??°???????????°??? S ????????????????????????????????£???????????????????????§
???????????´?????????????????°????????????????????????????????????
?????????merge???????????????????????°????????°?????±????????????????????????
"""

MAX = 1000000001

def merge(A, left, mid, right, 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 = A[left:mid]
    R = A[mid:right]

    L.append(MAX)
    R.append(MAX)
#    print("l:{} m:{} r:{} cnt:{} n1:{} n2:{}".format(left,mid,right,cnt,n1,n2))
#    print("left:{} right:{}".format(L,R))
    i = 0
    j = 0
    for k in range(left, right):
#        print("k:{} i:{} j:{}".format(k,i,j))
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
        cnt += 1
    return cnt

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

def main():
    """ ????????? """
    n = int(input())
    S = list(map(int,input().split()))
    cnt = mergeSort(S, 0, n, 0)
    print(" ".join(map(str,S)))
    print(cnt)

if __name__ == '__main__':
    main()