#
# def merge_sort(s)
#   tmp = s
#   return tmp if tmp.length <= 1
#   half(s).map { |e| e.merge_sort }
#   merge(a, b)
# end
#
# def half(s)
#   length = s.length
#   mid = (length/2)
#   a = s.slice!(0...mid)
#   b = s.slice!(mid..-1)
#   return [a, b]
# end
#
# def merge(a, b)
#   output = []
#   until a.empty? && b.empty?
#       if a.empty?
#         output.push(b.shift)
#       elsif b.empty?
#         output.push(a.shift)
#       elsif a.first <= b.first
#         output.push(a.shift)
#       else
#         b.shift
#       end
#       return output
#   end
# end
#
# p merge_sort([2, 4, 3, 7, 5, 67, 5,4,4, 8,7,6,5,546,362,245,56266,23,6,234,234,3425,25 ])





# def merge_sort(a, n)
#   return  if n <= 1
#
#   # a ?????????????????????
#   mid = n / 2
#   merge_sort(a, mid)
#
#   # a ???????????? b ???????????????????????????
#   b = a[mid..(n - 1)]
#   merge_sort(b, n - mid)
#
#   # a ???????????? a ?????????????????????
#   a[(n - mid)..(n - 1)] = a[0..(mid - 1)]
#
#   # a ???????????¨ b ?????§?°?????????????????????????
#   ri = 0
#   ai = n - mid
#   bi = 0
#   while bi < n - mid
#     if ai < n && a[ai] <= b[bi]
#       a[ri] = a[ai]
#       ai += 1
#     else
#       a[ri] = b[bi]
#       bi += 1
#     end
#     ri += 1
#   end
# end
@cnt = 0
def msort(a)
  l = a.length
  if l <= 1
    return a
  end
  al = msort(a[0..((l-1)/2)])
  ar = msort(a[((l+1)/2)..(l-1)])
  i = 0
  while i < l do
    if al[0] < ar[0]
      a[i] = al.shift
    else
      a[i] = ar.shift
    end
    i += 1
    if al.length == 0
      while i < l do
        a[i] = ar.shift
        i += 1
        @cnt += 1
      end
    elsif ar.length == 0
      while i < l do
        a[i] = al.shift
        i += 1
        @cnt += 1
      end
    end
     @cnt += 1
  end
  return a
end


n = gets.chomp.to_i
input_array = gets.chomp.split.map(&:to_i)
output = msort(input_array)
puts output
puts @cnt