import scala.io.StdIn.{readInt, readLine};

object Main {
    def main(args: Array[String]): Unit = {
        val n = readInt;
        val arr = readLine.split(" ").map(_.toLong);
        val cnt = mergeSort(arr, n);
        println(arr.mkString(" "));
        println(cnt);
        
    }
    def mergeSort(arr: Array[Long], n: Int): Int = {
        def _mergeSort(first: Int, last: Int): Int = {
            if (last - first > 0) {
                val pivot = (first + last) / 2;
                val cnt1 = _mergeSort(first, pivot);
                val cnt2 = _mergeSort(pivot + 1, last);
                merge(arr, first, last, pivot);
                cnt1 + cnt2 + (last - first + 1);
            } else {
                0;
            }
        }
        _mergeSort(0, n - 1);
    }
    
    def merge(arr: Array[Long], first: Int, last: Int, pivot: Int): Unit = {
        val tmpArr = (first to pivot).map(arr(_)).toArray;
        var ptr1 = 0;
        var ptr2 = pivot + 1;
        for (i <- (first to last)) {
            if (ptr1 >= tmpArr.length) {
                arr(i) = arr(ptr2);
                ptr2 += 1;
            } else if (ptr2 > last) {
                arr(i) = tmpArr(ptr1);
                ptr1 += 1;
            } else {
                if (arr(ptr2) < tmpArr(ptr1)) {
                    arr(i) = arr(ptr2);
                    ptr2 += 1;
                } else {
                    arr(i) = tmpArr(ptr1);
                    ptr1 += 1;
                }
            }
        }
    }
}

