import std.stdio, std.algorithm, std.range, std.conv, std.string;

int exchange = 0;

void main()
{
    int n = readln.chomp.to!int;
    auto s = readln.chomp.split.map!(to!int).array;
    mergeSort(s).map!(to!string).join(" ").writeln;
    exchange.writeln;
}

int[] merge(int[] left, int[] right)
{
    int[] result;

    while (true) {
        if (left.empty) {
            result ~= right;
            exchange += right.length;
            break;
        } else if (right.empty) {
            result ~= left;
            exchange += left.length;
            break;
        } else {
            if (left[0] <= right[0]) {
                result ~= left[0];
                left = left[1..$];
            } else {
                result ~= right[0];
                right = right[1..$];
            }

            exchange++;
        }
    }

    return result;
}

int[] mergeSort(int[] a)
{
    if (a.length < 2)
        return a;

    auto mid = a.length / 2;
    int[] left = a[0..mid];
    int[] right = a[mid..$];
    return merge(mergeSort(left),  mergeSort(right));
}