n = gets.to_i
sAry = gets.split.map(&:to_i)

INF = 10 ** 9 + 5
$nComp = 0

def merge(aAry, left, mid, right)
    # puts "aAry = " + aAry.to_s + ", left = " + left.to_s + ", mid = " +  mid.to_s + ", right = " + right.to_s
    n1 = mid - left
    n2 = right - mid
    # lAry = aAry[left, n1 - 1]
    # rAry = aAry[mid, n2 - 1]
    lAry = aAry[left, n1]
    rAry = aAry[mid, n2]
    lAry[n1] = INF
    rAry[n2] = INF
    # puts "lAry = " + lAry.to_s
    # puts "rAry = " + rAry.to_s
    i = 0
    j = 0
    (left..(right - 1)).each do |k|
        # puts "k = " + k.to_s
        if lAry[i] <= rAry[j] then
            aAry[k] = lAry[i]
            i += 1
        else
            aAry[k] = rAry[j]
            j += 1
        end
        $nComp += 1
    end
end

def mergeSort(aAry, left, right)
    if left + 1 < right then
        mid = (left + right) / 2
        mergeSort(aAry, left, mid)
        mergeSort(aAry, mid, right)
        merge(aAry, left, mid, right)
    end
end

mergeSort(sAry, 0, n)

puts sAry.join(' ')
puts $nComp
