package main

/*
マージソート
*/

import (
	"bufio"
	"bytes"
	"fmt"
	"log"
	"os"
	"strconv"
	"strings"
)

func merge(x, y []int) []int {

	// 2つの配列をマージする
	//   格納先を作る
	//   2つの配列の先頭から比較していき,小さい方を新たな格納先へ入れる
	//   どちらかがなくなったら在庫を全部入れる.

	xi := 0
	yi := 0
	arr := make([]int, len(x)+len(y))
	for k := range arr {
		if xi >= len(x) {
			arr[k] = y[yi]
			yi++
		} else if yi >= len(y) {
			arr[k] = x[xi]
			xi++
		} else if x[xi] <= y[yi] {
			arr[k] = x[xi]
			xi++
		} else {
			arr[k] = y[yi]
			yi++
		}
	}
	return arr
}

// 番兵あり
func mergeEx(x, y []int) []int {

	// 2つの配列をマージする
	//   比較用の配列をつくる． xの後ろにyを逆順にするのがミソ
	//   先頭と終端から比較していく．境界に番兵がいるためx,yの終端チェックを
	//   省くことができる
	wa := make([]int, len(x)+len(y))
	copy(wa, x)
	copy(wa[len(x):], reverse(y))

	arr := make([]int, len(x)+len(y))
	i := 0
	j := len(wa) - 1
	for k := 0; k < len(arr); k++ {
		if wa[i] < wa[j] {
			arr[k] = wa[i]
			i++
		} else {
			arr[k] = wa[j]
			j--
		}
	}
	return arr
}
func mergeSort(a []int) []int {
	if len(a) <= 1 {
		return a
	}
	mid := len(a) / 2
	// 左側をソートする
	left := mergeSort(a[0:mid])
	// 右側をソートする
	right := mergeSort(a[mid:])
	// マージする
	return mergeEx(left, right)
}

var count int

// 比較回数をカウントする機能付き
func mergeForA(x, y []int) []int {

	wa := append(x, reverse(y)...)

	arr := make([]int, len(x)+len(y))
	i := 0
	j := len(wa) - 1
	for k := 0; k < len(arr); k++ {
		if wa[i] < wa[j] {
			arr[k] = wa[i]
			i++
		} else {
			arr[k] = wa[j]
			j--
		}
		count++
	}
	return arr
}
func mergeSortForA(a []int) []int {
	if len(a) <= 1 {
		return a
	}
	mid := len(a) / 2
	// 左側をソートする
	left := mergeSortForA(a[0:mid])
	// 右側をソートする
	right := mergeSortForA(a[mid:])
	// マージする
	return mergeForA(left, right)
}

func init() {
	count = 0
}

func main() {
	scanner := makeScanner(10000000000 * 500000)
	eGetInt(scanner)
	s := eGetInts(scanner)
	m := mergeSortForA(s)
	fmt.Printf("%v\n", ints(m))
	fmt.Printf("%d\n", count)
}

////////////////////////////////////////////////////////////////////////////////
// ライブラリ
////////////////////////////////////////////////////////////////////////////////
func makeScanner(max int) *bufio.Scanner {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Buffer(make([]uint8, 0, 8192), max)
	return scanner
}
func eGetLine(r *bufio.Scanner) string {
	if r.Scan() {
		return r.Text()
	}
	err := r.Err()
	if err != nil {
		log.Fatal(err)
	}
	// EOF
	return ""
}
func eGetInt(r *bufio.Scanner) int {
	line := eGetLine(r)
	return eAtoi(line)
}
func eGetFields(r *bufio.Scanner) []string {
	line := eGetLine(r)
	return strings.Fields(line)
}
func eGetInts(r *bufio.Scanner) []int {
	fields := eGetFields(r)
	var ints []int
	for _, f := range fields {
		ints = append(ints, eAtoi(f))
	}
	return ints
}
func eGetChars(r *bufio.Scanner) []string {
	line := eGetLine(r)
	return strings.Split(line, "")
}
func eAtoi(s string) int {
	n, err := strconv.Atoi(s)
	if err != nil {
		log.Fatal(err)
	}
	return n
}

type ints []int

func (s ints) String() string {
	var buf bytes.Buffer
	sep := ""
	for _, v := range s {
		buf.WriteString(fmt.Sprintf("%s%d", sep, v))
		sep = " "
	}
	return buf.String()
}

func reverse(a ints) ints {
	r := make(ints, len(a))
	for i := 0; i < len(a); i++ {
		r[i] = a[len(a)-1-i]
	}
	return r
}
func max(a ints) (int, bool) {
	if len(a) == 0 {
		return 0, false
	}
	m := a[0]
	for _, e := range a {
		if e > m {
			m = e
		}
	}
	return m, true
}
func sum(a ints) int {
	if len(a) == 0 {
		return 0
	}
	sum := 0
	for _, e := range a {
		sum += e
	}
	return sum
}



Measured memory_bytes: 44376