fun main(args: Array<String>) {
    readLine()!!.toInt()
    val list = readLine()!!.split(' ').map { it.toInt() }

    val (sortedList, cnt) = mergeSort(list)

    println(sortedList.joinToString(" "))
    println(cnt)
}

private fun mergeSort(list: List<Int>): Pair<List<Int>, Int> {

    val array = list.toIntArray()
    var cnt = 0

    fun merge(left: Int, mid: Int, right: Int) {

        val leftArray = IntArray(mid - left + 1) { Int.MAX_VALUE }
        for (i in (0 until mid - left)) {
            leftArray[i] = array[left + i]
        }

        val rightArray = IntArray(right - mid + 1) { Int.MAX_VALUE }
        for (i in (0 until right - mid)) {
            rightArray[i] = array[mid + i]
        }

        var i = 0
        var j = 0

        for (k in left until right) {
            cnt++
            if (leftArray[i] <= rightArray[j]) {
                array[k] = leftArray[i++]
            } else {
                array[k] = rightArray[j++]
            }
        }
    }

    fun sort(left: Int, right: Int) {
        if (left + 1 < right) {
            val mid = (left + right) / 2
            sort(left, mid)
            sort(mid, right)
            merge(left, mid, right)
        }
    }

    sort(0, list.size)

    return array.toList() to cnt
}

