import scala.io.StdIn.{readInt, readLine}
object Main {
    def main(args: Array[String]): Unit = {
        val len = readInt
        val arr = readLine.split(" ").map(_.toInt)
        val n = mergeSort(arr, 0, len - 1)
        println(arr.mkString(" "))
        println(n)
    }
    def mergeSort(arr: Array[Int], left: Int, right: Int): Int = {
        if (right - left > 0) {
            val compare = right - left + 1
            val mid = (left + right) / 2
            val r1 = mergeSort(arr, left, mid)
            val r2 = mergeSort(arr, mid + 1, right)
            merge(arr, left, mid, right)
            compare + r2 + r1
        } else {
            0
        }
    }
    def merge(arr: Array[Int], left: Int, mid: Int, right: Int): Unit = {
        val leftHalfLen = mid - left + 1// 左半分の配列の要素数
        val tmp = arr.slice(left, mid + 1) // 左半分の配列 
        var leftPtr = 0
        var rightPtr = mid + 1
        for (i <- (left to right)) {
            if (leftPtr == leftHalfLen) {// 左半分を最後まで評価し終わった場合
                rightPtr += 1
            } else if (rightPtr == right + 1) { // 右半分を最後まで評価し終わった場合
                arr(i) = tmp(leftPtr)
                leftPtr += 1
            } else { // 左半分、右半分どちらも評価する要素が残っている場合
                if (tmp(leftPtr) <= arr(rightPtr)) {
                    arr(i) = tmp(leftPtr)
                    leftPtr += 1
                } else {
                    arr(i) = arr(rightPtr)
                    rightPtr += 1
                }
            }
        }
    }
}
