/* #region template */
use std::io::{stdin, stdout, Bytes, Read, Stdin, StdinLock, Stdout, StdoutLock, Write};
use std::str::FromStr;
#[allow(dead_code)]
struct Io<'a> {
    reader: Bytes<StdinLock<'a>>,
    writer: StdoutLock<'a>,
    in_buf: [u8; BUF_SIZE],
}
#[allow(dead_code)]
impl<'a> Io<'a> {
    fn new(stdin: &'a Stdin, stdout: &'a Stdout) -> Io<'a> {
        Io {
            reader: stdin.lock().bytes(),
            writer: stdout.lock(),
            in_buf: [0; BUF_SIZE],
        }
    }
    fn r<T: FromStr>(&mut self) -> T {
        let mut count = 0;
        loop {
            match self.reader.next() {
                Some(Ok(b' ')) | Some(Ok(b'\n')) => break,
                Some(Ok(c)) => self.in_buf[count] = c,
                _ => panic!(),
            }
            count += 1;
        }

        let s = unsafe { std::str::from_utf8_unchecked(&self.in_buf[0..count]) };
        s.parse().unwrap_or_else(|_| panic!())
    }
    fn ru(&mut self) -> usize {
        self.r()
    }
    fn iter<'b, T>(&'b mut self) -> IoIter<'a, 'b, T> {
        IoIter::new(self)
    }
    fn c<T: FromStr>(&mut self, n: usize) -> Vec<T> {
        self.iter().take(n).collect()
    }
    fn cu(&mut self, n: usize) -> Vec<usize> {
        self.c(n)
    }
    fn w<T: std::fmt::Display>(&mut self, v: T) {
        writeln!(self.writer, "{}", v).unwrap();
    }
    fn wn<T: std::fmt::Display>(&mut self, v: T) {
        write!(self.writer, "{}", v).unwrap();
    }
}
#[allow(dead_code)]
struct IoIter<'a: 'b, 'b, T> {
    io: &'b mut Io<'a>,
    m: std::marker::PhantomData<T>,
}
#[allow(dead_code)]
impl<'a: 'b, 'b, T> IoIter<'a, 'b, T> {
    fn new(io: &'b mut Io<'a>) -> IoIter<'a, 'b, T> {
        IoIter {
            io,
            m: std::marker::PhantomData,
        }
    }
}
impl<'a, 'b, T: FromStr> Iterator for IoIter<'a, 'b, T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        Some(self.io.r())
    }
}
fn main() {
    let stdin = stdin();
    let stdout = stdout();
    let mut io = Io::new(&stdin, &stdout);
    unsafe {
        solve(&mut io);
    }
}
/* #endregion */

const BUF_SIZE: usize = 1024;

unsafe fn solve(io: &mut Io) {
    let n = io.ru();
    let mut s = io.c::<u32>(n);
    let c = merge_sort(&mut s);

    s.get(0).map(|s0| io.wn(s0));
    for si in s.iter().skip(1) {
        io.wn(' ');
        io.wn(si);
    }
    io.wn('\n');
    io.w(c);
}

static mut BUF: [u32; 500000] = [0; 500000];
unsafe fn merge_sort(input: &mut [u32]) -> usize {
    unsafe fn inner(input: &mut [u32], left: usize, right: usize) -> usize {
        if left + 1 < right {
            let mid = (left + right) / 2;
            let mut count = inner(input, left, mid) + inner(input, mid, right);

            let mut i = 0;
            let mut j = 0;
            for k in 0.. {
                if i < mid - left {
                    if j < right - mid {
                        if input[left + i] >= input[mid + j] {
                            BUF[k] = input[mid + j];
                            j += 1;
                        } else {
                            BUF[k] = input[left + i];
                            i += 1;
                        }
                    } else {
                        BUF[k] = input[left + i];
                        i += 1;
                    }
                } else {
                    if j < right - mid {
                        BUF[k] = input[mid + j];
                        j += 1;
                    } else {
                        break;
                    }
                }
                count += 1;
            }

            for i in 0..right - left {
                input[left + i] = BUF[i];
            }

            count
        } else {
            0
        }
    }
    let len = input.len();
    inner(input, 0, len)
}



Measured memory_bytes: 8804