# Your code here!

n = gets.chomp.to_i
a = gets.chomp.split.map(&:to_i)

@count = 0

def merge(a, l, m, r)
  l_arr = a[l, m-l] << 10000000000000000000
  l_i = 0
  r_arr = a[m, r-m] << 10000000000000000000
  r_i = 0
  
  (l...r).each do |idx|
    # 小さい方から入れていく
    if l_arr[l_i] <= r_arr[r_i]
      a[idx] = l_arr[l_i]
      l_i+=1
    else
      a[idx] = r_arr[r_i]
      r_i+=1
    end
    @count += 1
  end
end

def merge_sort(a, left, right)
  if 1 < right-left
    mid = (right+left)/2
    merge_sort(a, left, mid)
    merge_sort(a, mid, right)
    merge(a, left, mid, right)
  end
end

merge_sort(a, 0, n)
puts a.map(&:to_s).join(' ')
p @count
