stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <cmath>

#include <cstdlib>

using namespace std;



const int MAX = 500010;

int n;

int a[MAX];

int tmp[MAX];

int com;



void merge(int A[], int lo, int mi, int hi) {

    int p1 = lo;

    int p2 = mi;

    int p3 = lo;

    while (p1 < mi && p2 < hi) {

        com++;

        if (A[p1] <= A[p2]) {

            tmp[p3++] = A[p1++];

        } else {

            tmp[p3++] = A[p2++];

        }

    }

    while (p1 < mi) {tmp[p3++] = A[p1++]; com++;}

    while (p2 < hi) {tmp[p3++] = A[p2++]; com++;}

    for (int i = lo; i < hi; i++) {

        A[i] = tmp[i];

    }

}



void mergeSort(int A[], int lo, int hi) {

    if (lo + 1 < hi) {

        int mi = (lo + hi) >> 1;

        mergeSort(A, lo, mi);

        mergeSort(A, mi, hi);

        merge(A, lo, mi, hi);

    }

}





int main() {

    //freopen("in.txt", "r", stdin);

    //freopen("out.txt", "w", stdout);

    scanf("%d", &n);

    com = 0;

    for (int i = 0; i < n; i++) {

        scanf("%d", &a[i]);

    }

    mergeSort(a, 0, n);

    for (int i = 0; i < n; i++) {

        if (i > 0) printf(" ");

        printf("%d", a[i]);

    }

    printf("\n");

    printf("%d\n", com);

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.076369766687646x):
//#define LOCAL



#include <cstdio>



#define M 500010

#define SENTINEL 2000000000

int s = 0, A[M], L[M], R[M];



void merge(int l, int m, int r) {

	int i, j, k, n1 = m-l, n2 = r-m;

	L[n1] = R[n2] = SENTINEL;

	for(i=0; i<n1; ++i) L[i] = A[l+i];

	for(i=0; i<n2; ++i) R[i] = A[m+i];

	i = j = 0;

	for(k=l; k<r; ++k) {

		if(L[i] <= R[j]) A[k] = L[i++];

		else A[k] = R[j++]; ++s;

	}

}



void mergeSort(int l, int r) {

	if(l+1 < r) {

		int m = (l+r)/2;

		mergeSort(l, m);

		mergeSort(m, r);

		merge(l, m, r);

	}

}



int main()

{

	#ifdef LOCAL

		freopen("E:\\Temp\\input.txt", "r", stdin);

		freopen("E:\\Temp\\output.txt", "w", stdout);

	#endif



	int i, n;

	scanf("%d", &n);

	for(i=0; i<n; ++i) scanf("%d", &A[i]);



	mergeSort(0, n);

	for(i=0; i<n; ++i) {

		if(i) printf(" ");

		printf("%d", A[i]);

	}

	printf("\n%d\n", s);



	return 0;

}
// Slower C++ solution:
#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <cmath>

#include <cstdlib>

using namespace std;



const int MAX = 500010;

int n;

int a[MAX];

int tmp[MAX];

int com;



void merge(int A[], int lo, int mi, int hi) {

    int p1 = lo;

    int p2 = mi;

    int p3 = lo;

    while (p1 < mi && p2 < hi) {

        com++;

        if (A[p1] <= A[p2]) {

            tmp[p3++] = A[p1++];

        } else {

            tmp[p3++] = A[p2++];

        }

    }

    while (p1 < mi) {tmp[p3++] = A[p1++]; com++;}

    while (p2 < hi) {tmp[p3++] = A[p2++]; com++;}

    for (int i = lo; i < hi; i++) {

        A[i] = tmp[i];

    }

}



void mergeSort(int A[], int lo, int hi) {

    if (lo + 1 < hi) {

        int mi = (lo + hi) >> 1;

        mergeSort(A, lo, mi);

        mergeSort(A, mi, hi);

        merge(A, lo, mi, hi);

    }

}





int main() {

    //freopen("in.txt", "r", stdin);

    //freopen("out.txt", "w", stdout);

    scanf("%d", &n);

    com = 0;

    for (int i = 0; i < n; i++) {

        scanf("%d", &a[i]);

    }

    mergeSort(a, 0, n);

    for (int i = 0; i < n; i++) {

        if (i > 0) printf(" ");

        printf("%d", a[i]);

    }

    printf("\n");

    printf("%d\n", com);

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.063670388954537x):
//

// Created by Nivras on 2017/5/25.

//



#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

using namespace std;



const int MAXN = 550000;

const int INF = 1000000007;



int cnt = 0;

int leftNum[MAXN], rightNum[MAXN];

int num[MAXN];



void merge(int num[], int left, int mid, int right) {

    for (int i = 0; i < mid - left; i++) {

        leftNum[i] = num[left + i];

    }

    leftNum[mid - left] = INF;



    for (int i = 0; i < right - mid; i++) {

        rightNum[i] = num[mid + i];

    }

    rightNum[right - mid] = INF;



    int leftpre = 0;

    int rightpre = 0;

    for (int i = 0; i < right - left; i++) {

        cnt++;

        if (leftNum[leftpre] <= rightNum[rightpre]) {

            num[left + i] = leftNum[leftpre];

            leftpre++;

        }

        else {

            num[left + i] = rightNum[rightpre];

            rightpre++;

        }

    }

}



void mergeSort(int num[], int left, int right) {

    if (left + 1 < right) {

        int mid = (left + right) / 2;

        mergeSort(num, left, mid);

        mergeSort(num, mid, right);

        merge(num, left, mid, right);

    }

}



int main()

{

    int n;

    scanf("%d", &n);

    for (int i = 0; i < n; i++) {

        scanf("%d", &num[i]);

    }

    cnt = 0;

    mergeSort(num, 0, n);



    for (int i = 0; i < n; ++i) {

        if (i != 0) {

            printf(" ");

        }

        printf("%d", num[i]);

    }

    puts("");

    printf("%d\n", cnt);



    return 0;

}
// Slower C++ solution:
#include<iostream>

#include<stdio.h>

#define MAX 500000

#define INFTY 2000000000



int L[MAX / 2 + 2], R[MAX / 2 + 2];

int cnt;



void merge(int A[], int left, int mid, int right){

	int n1 = mid - left;

	int n2 = right - mid;

	int i;

	int L[n1], R[n2];

	for (i = 0; i < n1; i++){

		L[i] = A[left + i];

	}

	for (i = 0; i < n2; i++){

		R[i] = A[mid + i];

	}

	L[n1] = INFTY;

	R[n2] = INFTY;

	i = 0;

	int j = 0;

	for (int k = left; k < right; k++){

		cnt++;

		if (L[i] <= R[j]){

			A[k] = L[i];

			i = i + 1;

		}

		else{

			A[k] = R[j];

			j = j + 1;

		}

	}

}



void mergeSort(int A[],int n, int left, int right){

	int mid;

	if (left + 1 < right){

		mid = (left + right) / 2;

		mergeSort(A, n, left, mid);

		mergeSort(A, n, mid, right);

		merge(A, left, mid, right);

	}

}



int main(){

	int A[MAX],n,i;

	cnt = 0;

	scanf("%d", &n);

	for (i = 0; i < n; i++){

		scanf("%d", &A[i]);

	}

	mergeSort(A, n, 0, n);

	for (int i = 0; i < n; i++){

		if (i)

			printf(" ");

		printf("%d", A[i]);

	}

	printf("\n");

	printf("%d\n", cnt);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.310347354099478x):
#include<stdio.h>

#define MAX 500000

#define INFTY 2000000000



int L[MAX / 2 + 1], R[MAX / 2 + 1];

int A[MAX];

int cnt = 0;



void merge(int A[], int left, int mid, int right){

	int i,j;

	int n1 = mid - left;

	int n2 = right - mid;

	for (i = 0; i < n1; i++){

		L[i] = A[left+i];

	}

	for (i = 0; i < n2; i++){

		R[i] = A[mid+i];

	}

	L[n1] = R[n2] = INFTY;

        i=0;

        j=0;

	for (int k = left; k < right; k++){

		cnt++;

		if (L[i] <= R[j]){

			A[k] = L[i++];

		}

		else{

			A[k] = R[j++];

		}

	}

}



void mergeSort(int A[], int left, int right){

	if (left + 1 < right){

		int mid = (left + right) / 2;

		mergeSort(A, left, mid);

		mergeSort(A, mid, right);

		merge(A, left, mid, right);

	}

}



int main(){

	int n;

	scanf("%d", &n);

	for (int i = 0; i < n; i++){

		scanf("%d", &A[i]);

	}

	mergeSort(A, 0, n);

	for (int i = 0; i < n; i++){

		if (i)printf(" ");

		printf("%d", A[i]);

	}

	printf("\n");

        printf("%d\n",cnt);

	return 0;

}
// Slower C++ solution:
#include<iostream>

using namespace std;



#define INFTY 1 << 30;







int Merge(int A[],int left,int mid,int right){



  int k;

  int n1 = mid-left;

  int n2 = right-mid;



  int L[n1+1];

  int R[n2+1];



  for(int i=0;i<n1;i++){

    L[i] = A[left+i];

  }



  for(int i=0;i<n2;i++){

    R[i] = A[mid+i];

  }



  L[n1] = INFTY;

  R[n2] = INFTY;



  int i=0;

  int j=0;



  for(k=left;k<right;k++){

    if(L[i]<=R[j]){

      A[k] = L[i];

      i++;

    }else{

      A[k] = R[j];

      j++;

    }

  }

  return k - left;

}



int MergeSort(int A[],int left,int right){

  int count = 0;

  if(left+1 < right){

    int mid = (left+right)/2;

    count += MergeSort(A,left,mid);

    count += MergeSort(A,mid,right);

    count += Merge(A,left,mid,right);

  }

  return count;

}



int main(){

  int n,m;

  cin >> n;



  int S[500000];

  for(int i=0;i<n;i++){

    cin >> S[i];

  }



  m = MergeSort(S,0,n);



  for(int i=0;i<n-1;i++){

    cout << S[i];

    cout << " ";

  }

  cout << S[n-1];

  cout << endl;



  cout << m << endl;



  return 0;

}




// Faster C++ solution for the same problem (measured speedup: 4.366376278413133x):
#include<stdio.h>



#define INFTY 1 << 30;







int Merge(int A[],int left,int mid,int right){



  int k;

  int n1 = mid-left;

  int n2 = right-mid;



  int L[n1+1];

  int R[n2+1];



  for(int i=0;i<n1;i++){

    L[i] = A[left+i];

  }



  for(int i=0;i<n2;i++){

    R[i] = A[mid+i];

  }



  L[n1] = INFTY;

  R[n2] = INFTY;



  int i=0;

  int j=0;



  for(k=left;k<right;k++){

    if(L[i]<=R[j]){

      A[k] = L[i];

      i++;

    }else{

      A[k] = R[j];

      j++;

    }

  }

  return k - left;

}



int MergeSort(int A[],int left,int right){

  int count = 0;

  if(left+1 < right){

    int mid = (left+right)/2;

    count += MergeSort(A,left,mid);

    count += MergeSort(A,mid,right);

    count += Merge(A,left,mid,right);

  }

  return count;

}



int main(){

  int n,m;

  scanf("%d",&n);



  int S[500000];

  for(int i=0;i<n;i++){

    scanf("%d",&S[i]);

  }



  m = MergeSort(S,0,n);



  for(int i=0;i<n-1;i++){

    printf("%d ",S[i]);

  }

  printf("%d\n%d\n",S[n-1],m);



  return 0;

}
// Slower C++ solution:
#include<iostream>

#include<vector>

#define INF 1000000000

#define nmax 500005

using namespace std;



int n;

int cnt = 0;

int a[nmax];



void merge(int left, int mid, int right){

  int n1 = mid -left;

  int n2 = right - mid;

  int l[nmax];

  int r[nmax];



  int i, j;

  

  for(i = 0; i < n1; i++) l[i] = a[left + i];

  for(i = 0; i < n2; i++) r[i] = a[mid + i];



  l[n1] = INF;

  r[n2] = INF;



  i = 0;

  j = 0;



  for(int k = left; k < right; k++){

    if(l[i] <= r[j]) a[k] = l[i++];



    else a[k] = r[j++];



    cnt++;

    

  }

}



void mergeSort(int left, int right){

  if(left+1 < right){

    int mid = (left + right) / 2;



    mergeSort(left, mid);

    mergeSort(mid, right);

    merge(left, mid, right);

  }

}



int main()

{

  cin >> n;

  for(int i = 0; i < n; i++) cin >> a[i];



  mergeSort(0, n);



  for(int i = 0; i < n; i++){

    if(i) cout << " ";



    cout << a[i];

  }



  cout << endl;

  cout << cnt << endl;

  



  return 0;



}




// Faster C++ solution for the same problem (measured speedup: 1.1411884465970321x):
#include<iostream>

#include<vector>

#define INF 1000000000

#define nmax 500005

using namespace std;



int n;

int cnt = 0;

vector<int> a;



void merge(int left, int mid, int right){

  int n1 = mid -left;

  int n2 = right - mid;

  vector<int> l(n1+5);

  vector<int> r(n1+5);



  int i, j;

  

  for(i = 0; i < n1; i++) l[i] = a[left + i];

  for(i = 0; i < n2; i++) r[i] = a[mid + i];



  l[n1] = INF;

  r[n2] = INF;



  i = 0;

  j = 0;



  for(int k = left; k < right; k++){

    if(l[i] <= r[j]) a[k] = l[i++];



    else a[k] = r[j++];



    cnt++;

    

  }

}



void mergeSort(int left, int right){

  if(left+1 < right){

    int mid = (left + right) / 2;



    mergeSort(left, mid);

    mergeSort(mid, right);

    merge(left, mid, right);

  }

}



int main()

{

  cin >> n;

  a.resize(n);

  

  for(int i = 0; i < n; i++) cin >> a[i];



  mergeSort(0, n);



  for(int i = 0; i < n; i++){

    if(i) cout << " ";



    cout << a[i];

  }



  cout << endl;

  cout << cnt << endl;

  



  return 0;



}
// Slower C++ solution:
#include <iostream>

#include <string>

#include <algorithm>

#include <cstdio>



using namespace std;



const int INF = 1000000001;

const int MAX = 500000;

int cnt;

int L[1 + MAX/2] = {0},R[1 + MAX/2] = {0};





void merge(int* A,int left,int mid,int right)

{

	int n1,n2,n,i,j;

	//int L[1 + MAX/2] = {0},R[1 + MAX/2] = {0};

	n1 = mid - left;

	n2 = right - mid;



	for(int i = 0; i < n1; i++)

	{

		L[i] = A[left + i];

	}

	for(int i = 0; i < n2; i++)

	{

		R[i] = A[mid + i];

	}



	L[n1] = INF;

	R[n2] = INF;



	i = 0;

	j = 0;



	//cout << "right=" << right << "left=" << left << endl;

	//cout << "right - left= " << right << " - " << left << " = " << right - left << endl;



	for(int k = 0; k < right - left; k++)

	{

		if (L[i] <= R[j] )

		{

			A[left + k] = L[i];

			i++;

		}else

		{

			A[left + k] = R[j];

			j++;

		}



		cnt++;

	}



	//return cnt;

}





void mergesort(int* A,int left,int right)

{

	int mid,sol, sol_left, sol_right;



	if(left + 1 < right)

	{

		mid = (left + right) / 2;

		//cout << "mid=" << mid << endl;

		//sol_left = mergesort(A,left,mid);

		//sol_right = mergesort(A,mid,right);

		//sol = merge(A,left,mid,right) + sol_right + sol_left;



		mergesort(A,left,mid);

		mergesort(A,mid,right);

		merge(A,left,mid,right);



		//cout << "sol= " << sol << endl;

	}



	//return sol;

}



int main()

{

	int N,S[MAX] = {0},solution;

	cnt = 0;



	cin >> N;



	for(int i = 0; i < N; i++)

	{

		cin >> S[i];

	}



	//solution = mergesort(S,0,N);

	mergesort(S,0,N);



	for(int i = 0; i < N; i++)

	{

		if (i == N-1)

		{

			cout << S[i] <<endl;

		}else

		{

			cout << S[i] << " ";

		}

	}



	cout << cnt << endl;



	return 0;

}

	

// Faster C++ solution for the same problem (measured speedup: 3.021927424205401x):
#include <iostream>

#include <string>

#include <algorithm>

#include <cstdio>



using namespace std;



const int INF = 1000000001;

const int MAX = 500000;

int cnt;

int S[MAX] = {0}, L[1 + MAX/2] = {0}, R[1 + MAX/2] = {0};





void merge(int* A,int left,int mid,int right)

{

	int n1,n2,n,i,j;

	n1 = mid - left;

	n2 = right - mid;



	for(int i = 0; i < n1; i++)

	{

		L[i] = A[left + i];

	}

	for(int i = 0; i < n2; i++)

	{

		R[i] = A[mid + i];

	}



	L[n1] = INF;

	R[n2] = INF;



	i = 0;

	j = 0;



	for(int k = 0; k < right - left; k++)

	{

		if (L[i] <= R[j] )

		{

			A[left + k] = L[i];

			i++;

		}else

		{

			A[left + k] = R[j];

			j++;

		}



		cnt++;

	}

}





void mergesort(int* A,int left,int right)

{

	int mid;



	if(left + 1 < right)

	{

		mid = (left + right) / 2;

		mergesort(A,left,mid);

		mergesort(A,mid,right);

		merge(A,left,mid,right);

	}

}



int main()

{

	int N;

	cnt = 0;



	cin >> N;



	for(int i = 0; i < N; i++)

	{

		cin >> S[i];

	}



	mergesort(S,0,N);



	for(int i = 0; i < N; i++)

	{

		if (i == N-1)

		{

			cout << S[i] <<endl;

		}else

		{

			cout << S[i] << " ";

		}

	}



	cout << cnt << endl;



	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <string>

#include <algorithm>

#include <cstdio>



using namespace std;



const int INF = 1000000001;

const int MAX = 500000;

int cnt;

int L[1 + MAX/2] = {0},R[1 + MAX/2] = {0};





void merge(int* A,int left,int mid,int right)

{

	int n1,n2,n,i,j;

	//int L[1 + MAX/2] = {0},R[1 + MAX/2] = {0};

	n1 = mid - left;

	n2 = right - mid;



	for(int i = 0; i < n1; i++)

	{

		L[i] = A[left + i];

	}

	for(int i = 0; i < n2; i++)

	{

		R[i] = A[mid + i];

	}



	L[n1] = INF;

	R[n2] = INF;



	i = 0;

	j = 0;



	//cout << "right=" << right << "left=" << left << endl;

	//cout << "right - left= " << right << " - " << left << " = " << right - left << endl;



	for(int k = 0; k < right - left; k++)

	{

		if (L[i] <= R[j] )

		{

			A[left + k] = L[i];

			i++;

		}else

		{

			A[left + k] = R[j];

			j++;

		}



		cnt++;

	}



	//return cnt;

}





void mergesort(int* A,int left,int right)

{

	int mid,sol, sol_left, sol_right;



	if(left + 1 < right)

	{

		mid = (left + right) / 2;

		//cout << "mid=" << mid << endl;

		//sol_left = mergesort(A,left,mid);

		//sol_right = mergesort(A,mid,right);

		//sol = merge(A,left,mid,right) + sol_right + sol_left;



		mergesort(A,left,mid);

		mergesort(A,mid,right);

		merge(A,left,mid,right);



		//cout << "sol= " << sol << endl;

	}



	//return sol;

}



int main()

{

	int N,S[MAX] = {0},solution;

	cnt = 0;



	cin >> N;



	for(int i = 0; i < N; i++)

	{

		cin >> S[i];

	}



	//solution = mergesort(S,0,N);

	mergesort(S,0,N);



	for(int i = 0; i < N; i++)

	{

		if (i == N-1)

		{

			cout << S[i] <<endl;

		}else

		{

			cout << S[i] << " ";

		}

	}



	cout << cnt << endl;



	return 0;

}

	

// Faster C++ solution for the same problem (measured speedup: 3.021810748791041x):
#include <iostream>





using namespace std;



const int INF = 1000000001;

const int MAX = 500000;

int cnt,N;

int S[MAX] = {0}, L[1 + MAX/2] = {0}, R[1 + MAX/2] = {0};





void merge(int* A,int left,int mid,int right)

{

	int n1,n2,i,j;

	n1 = mid - left;

	n2 = right - mid;



	for(int i = 0; i < n1; i++)

	{

		L[i] = A[left + i];

	}

	for(int i = 0; i < n2; i++)

	{

		R[i] = A[mid + i];

	}



	L[n1] = INF;

	R[n2] = INF;



	i = 0;

	j = 0;



	for(int k = 0; k < right - left; k++)

	{

		if (L[i] <= R[j] )

		{

			A[left + k] = L[i];

			i++;

		}else

		{

			A[left + k] = R[j];

			j++;

		}



		cnt++;

	}

}





void mergesort(int* A,int left,int right)

{

	int mid;



	if(left + 1 < right)

	{

		mid = (left + right) / 2;

		mergesort(A,left,mid);

		mergesort(A,mid,right);

		merge(A,left,mid,right);

	}

}



int main()

{

	cnt = 0;



	cin >> N;



	for(int i = 0; i < N; i++)

	{

		cin >> S[i];

	}



	mergesort(S,0,N);



	for(int i = 0; i < N; i++)

	{

		if (i == N-1)

		{

			cout << S[i] <<endl;

		}else

		{

			cout << S[i] << " ";

		}

	}



	cout << cnt << endl;



	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <string>

#include <algorithm>

#include <cstdio>



using namespace std;



const int INF = 1000000001;

const int MAX = 500000;

int cnt;

int L[1 + MAX/2] = {0},R[1 + MAX/2] = {0};





void merge(int* A,int left,int mid,int right)

{

	int n1,n2,n,i,j;

	//int L[1 + MAX/2] = {0},R[1 + MAX/2] = {0};

	n1 = mid - left;

	n2 = right - mid;



	for(int i = 0; i < n1; i++)

	{

		L[i] = A[left + i];

	}

	for(int i = 0; i < n2; i++)

	{

		R[i] = A[mid + i];

	}



	L[n1] = INF;

	R[n2] = INF;



	i = 0;

	j = 0;



	//cout << "right=" << right << "left=" << left << endl;

	//cout << "right - left= " << right << " - " << left << " = " << right - left << endl;



	for(int k = 0; k < right - left; k++)

	{

		if (L[i] <= R[j] )

		{

			A[left + k] = L[i];

			i++;

		}else

		{

			A[left + k] = R[j];

			j++;

		}



		cnt++;

	}



	//return cnt;

}





void mergesort(int* A,int left,int right)

{

	int mid,sol, sol_left, sol_right;



	if(left + 1 < right)

	{

		mid = (left + right) / 2;

		//cout << "mid=" << mid << endl;

		//sol_left = mergesort(A,left,mid);

		//sol_right = mergesort(A,mid,right);

		//sol = merge(A,left,mid,right) + sol_right + sol_left;



		mergesort(A,left,mid);

		mergesort(A,mid,right);

		merge(A,left,mid,right);



		//cout << "sol= " << sol << endl;

	}



	//return sol;

}



int main()

{

	int N,S[MAX] = {0},solution;

	cnt = 0;



	cin >> N;



	for(int i = 0; i < N; i++)

	{

		cin >> S[i];

	}



	//solution = mergesort(S,0,N);

	mergesort(S,0,N);



	for(int i = 0; i < N; i++)

	{

		if (i == N-1)

		{

			cout << S[i] <<endl;

		}else

		{

			cout << S[i] << " ";

		}

	}



	cout << cnt << endl;



	return 0;

}

	

// Faster C++ solution for the same problem (measured speedup: 3.0626553591331613x):
#include <iostream>

#include <cstdio>





using namespace std;



const int INF = 1000000001;

const int MAX = 500000;

int cnt,N;

int S[MAX] = {0}, L[1 + MAX/2] = {0}, R[1 + MAX/2] = {0};





void merge(int* A,int left,int mid,int right)

{

	int n1,n2,i,j;

	n1 = mid - left;

	n2 = right - mid;



	for(int i = 0; i < n1; i++)

	{

		L[i] = A[left + i];

	}

	for(int i = 0; i < n2; i++)

	{

		R[i] = A[mid + i];

	}



	L[n1] = INF;

	R[n2] = INF;



	i = 0;

	j = 0;



	for(int k = 0; k < right - left; k++)

	{

		if (L[i] <= R[j] )

		{

			A[left + k] = L[i];

			i++;

		}else

		{

			A[left + k] = R[j];

			j++;

		}



		cnt++;

	}

}





void mergesort(int* A,int left,int right)

{

	int mid;



	if(left + 1 < right)

	{

		mid = (left + right) / 2;

		mergesort(A,left,mid);

		mergesort(A,mid,right);

		merge(A,left,mid,right);

	}

}



int main()

{

	cnt = 0;



	scanf("%d", &N);



	for(int i = 0; i < N; i++)

	{

		scanf("%d", &S[i]);

	}



	mergesort(S,0,N);



	for(int i = 0; i < N; i++)

	{

		if (i == N-1)

		{

			printf("%d\n", S[i]);

		}else

		{

			printf("%d ", S[i]);

		}

	}



	printf("%d\n", cnt);

	return 0;

}
// Slower C++ solution:
#include<iostream>

using namespace std;



#define SIZE 500000

#define INFTY 1200000000

int count = 0;



void show(int* a, int size)

{

    int i;

    cout << a[0];

    for(i = 1; i < size; i++) cout << " " << a[i];

    cout << endl;

}



void Merge(int* A, int left, int mid, int right)

{

    int R[SIZE], L[SIZE];

    int i, j, k, n1, n2;

    n1 = mid - left;

    n2 = right - mid;

    for(i = 0; i < n1; i++) L[i] = A[i + left];

    for(j = 0; j < n2; j++) R[j] = A[j + mid];



    L[n1] = INFTY;

    R[n2] = INFTY;

    i = j = 0;



    for(k = left; k < right; k++){

        if(L[i] <= R[j]){

            A[k] = L[i];

            i++;

        }else{

            A[k] = R[j];

            j++;

        }

        count++;

    }

}



void MergeSort(int* A, int left, int right)

{

    int mid;

    if(left + 1 < right){

        mid = (left + right) / 2;

        MergeSort(A, left, mid);

        MergeSort(A, mid, right);

        Merge(A, left, mid, right);

    }

    return;

}



int main()

{

    int i, n, S[SIZE];

    cin >> n;

    for(i = 0; i < n; i++) cin >> S[i];



    MergeSort(S, 0, n);

    show(S, n);

    cout << count << endl;



    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.1242916806718566x):
#include<stdio.h>



#define SIZE 500000

#define INFTY 1200000000

int count = 0;



void show(int* a, int size)

{

    int i;

    printf("%d", a[0]);

    for(i = 1; i < size; i++) printf(" %d", a[i]);

	printf("\n");

}



void Merge(int* A, int left, int mid, int right)

{

    int R[SIZE], L[SIZE];

    int i, j, k, n1, n2;

    n1 = mid - left;

    n2 = right - mid;

    for(i = 0; i < n1; i++) L[i] = A[i + left];

    for(j = 0; j < n2; j++) R[j] = A[j + mid];



    L[n1] = INFTY;

    R[n2] = INFTY;

    i = j = 0;



    for(k = left; k < right; k++){



		if(L[i] <= R[j]){ A[k] = L[i]; i++; }



        else{ A[k] = R[j]; j++; }



        count++;

    }

}



void MergeSort(int* A, int left, int right)

{

    int mid;

    if(left + 1 < right){

        mid = (left + right) / 2;

        MergeSort(A, left, mid);

        MergeSort(A, mid, right);

        Merge(A, left, mid, right);

    }

    return;

}



int main()

{

    int i, n, S[SIZE];

    scanf("%d", &n);

    for(i = 0; i < n; i++) scanf("%d", &S[i]);



    MergeSort(S, 0, n);

    show(S, n);

    printf("%d\n", count);



    return 0;

}