Write a program of a Merge Sort algorithm implemented by the following pseudocode. You should also report the number of comparisons in the Merge function.


Merge(A, left, mid, right)
n1 = mid - left;
n2 = right - mid;
create array L[0...n1], R[0...n2]
for i = 0 to n1-1
do L[i] = A[left + i]
for i = 0 to n2-1
do R[i] = A[mid + i]
L[n1] = SENTINEL
R[n2] = SENTINEL
i = 0;
j = 0;
for k = left to right-1
if L[i] <= R[j]
then A[k] = L[i]
i = i + 1
else A[k] = R[j]
j = j + 1

Merge-Sort(A, left, right){
if left+1 < right
then mid = (left + right)/2;
call Merge-Sort(A, left, mid)
call Merge-Sort(A, mid, right)
call Merge(A, left, mid, right)


Notes

Constraints

* n ≤ 500000
* 0 ≤ an element in S ≤ 109

Input

In the first line n is given. In the second line, n integers are given.

Output

In the first line, print the sequence S. Two consequtive elements should be separated by a space character.

In the second line, print the number of comparisons.

Example

Input

10
8 5 9 2 6 3 7 1 10 4


Output

1 2 3 4 5 6 7 8 9 10
34
#include <stdio.h>
int a[1000000];
long long int ans;
void mergesort(int l,int r){
	if(l==r)return;
	if(l==r-1){
		ans+=2;
		if(a[r]<a[l]){
			int temp;
			temp=a[l];
			a[l]=a[r];
			a[r]=temp;
		}
		return;
	}
	int mid=(l+r)/2,now=0,b[r-l+1];
	mergesort(l,mid);
	mergesort(mid+1,r);
	for(int i=0;i<=r-l;i++){
	if(a[l+i-now]<a[mid+1+now]){
		b[i]=a[i+l-now];
		if(i+l-now==mid){
			for(i++;i<=r-l;i++)b[i]=a[i+l];
		}
	}
	else{
		b[i]=a[mid+1+now];
		now++;
		if(mid+now==r){
			for(i++;i<=r-l;i++){
				b[i]=a[i+l-now];
			}
		}
	}
	}
	for(int i=0;i<=r-l;i++){
		a[i+l]=b[i];
	}
	ans+=r-l+1;
}
int main(){
	int n;	
scanf("%d",&n);
ans=0;
	for(int i=0;i<n;i++)scanf("%d",&a[i]);
	mergesort(0,n-1);
	printf("%d",a[0]);
	for(int i=1;i<n;i++)printf("% d",a[i]);
	printf("\n%lld\n",ans);
}