#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Loop(i, n) for(int i = 0; i < (int)n; i++)
#define Loop1(i, n) for(int i = 1; i <= (int)n; i++)
#define Loopr(i, n) for(int i = (int)n - 1; i >= 0; i--)
#define INF (int)2e9
#pragma warning (disable: 4996)

static const int N = 1000;

int cnt = 0;

void merging(int *a, int s, int m, int t) {
	const int n1 = m - s + 1;
	const int n2 = t - m + 1;
	int *l = malloc(sizeof(int)*n1), *r = malloc(sizeof(int)*n2);
	Loop(i, n1 - 1) l[i] = a[s + i];
	Loop(i, n2 - 1) r[i] = a[m + i];
	l[n1 - 1] = INF;
	r[n2 - 1] = INF;
	int i = 0, j = 0, k;
	for (k = s;k < t;k++) {
		if (l[i] <= r[j]) {
			a[k] = l[i];
			i++;
		}
		else {
			a[k] = r[j];
			j++;
		}
		cnt++;
	}
	free(l);
	free(r);
	return;
}


void merge_sort(int *a, int s, int t) {
	if (s + 1 < t) {
		int m = (s + t) / 2;
		merge_sort(a, s, m);
		merge_sort(a, m, t);
		merging(a, s, m, t);
	}
	return;
}

int main() {
	int n;
	scanf("%d", &n);
	int *a = malloc(sizeof(int)*n);
	Loop(i, n) scanf("%d", &a[i]);
	merge_sort(a, 0, n);
	printf("%d", a[0]);
	Loop1(i, n - 1) printf(" %d", a[i]);
	printf("\n%d\n", cnt);

	return 0;
}

/*
int main() {
	a = malloc(sizeof(char*)*N);
	Loop(i, N) {
		a[i] = malloc(sizeof(char) * 100);
	}
	b = malloc(sizeof(char*)*N);
	Loop(i, N) {
		b[i] = malloc(sizeof(char) * 100);
	}
	int n = N;
	Loop(i, N) {
		if (scanf("%99s", a[i]) == EOF) {
			n = i;
			break;
		}
	}
	qsort(a, n, sizeof(char*), cmp);
	Loop(i, n) {
		printf("%s\n", a[i]);
	}
	system("pause");
	return 0;
}
*/