#include <stdio.h>

int iteracije = 0;

void swap( int *x, int *y )
{
	int k = *x;
	*x = *y;
	*y = k;
}

void insertionSort( int *a, int n )
{
	for ( int i = 1; i < n; i ++ )
	{
		int p = a[ i ];
		int j;
		for ( j = i - 1; j >= 0 && a[ j ] > p; j -- )
			a[ j + 1 ] = a[ j ];
		a[ j + 1 ] = p;
	}
}

void selectionSort( int *a, int n )
{
	for ( int i = 0; i < n - 1; i ++ )
		for ( int j = i + 1; j < n; j ++ )
			if ( a[ i ] > a[ j ] )
				swap( a + i, a + j );
}

void bubbleSort( int *a, int n )
{
	for( int i = n - 1; i; i--)
    	for( int j = 0; j < i; j ++ )
      		if ( a[ j ] > a[ j + 1 ] )
			{
				swap( a + j, a + j + 1 );
				iteracije ++;
			}
}


void bubbleSort2( int *a, int n )
{
	int swp = 1;
	for( int i = n - 1; swp & i; i--)
	{
		swp = 0;
    	for( int j = 0; j < i; j ++ )
      		if ( a[ j ] > a[ j + 1 ] )
			{
				swap( a + j, a + j + 1 );
				swp = 1;
				iteracije ++;
			}
	}
}

void merge( int *a, int l, int m, int r )
{
	int n1 = m - l + 1;
	int n2 = r - m;

	int L[ n1 ], R[ n2 ];
	for ( int i = 0; i < n1; i ++ )
		L[ i ] = a[ l + i ];
	for ( int i = 0; i < n2; i ++ )
		R[ i ] = a[ m + 1 + i ];

	int i = 0;
	int j = 0;
	int k  = l;
	while ( i < n1 && j < n2 )
		if ( L[ i ] <= R[ j ] )
			a[ k ++ ] = L[ i ++ ];
		else
			a[ k ++ ] = R[ j ++ ];

	while ( i < n1 )
		a[ k ++ ] = L[ i ++ ];

	while ( j < n2 )
		a[ k ++ ] = R[ j ++ ];
}

void merge_Sort( int *a, int l, int r )
{
	if ( l < r )
	{
		int m = ( l + r ) / 2; // l + ( r - l ) / 2

		merge_Sort( a, l, m );
		merge_Sort( a, m + 1, r );

		merge( a, l, m, r );
	}
}

void mergeSort( int *a, int n )
{
	merge_Sort( a, 0, n - 1 );
}

int main()
{
	int n;
	scanf("%d", &n );
	
	int a[ n ];
	for ( int i = 0; i < n; i ++ )
		scanf("%d", a + i );
	
	bubbleSort2( a, n );

	for ( int i = 0; i < n; i ++ )
		printf("%d ", a[ i ] );
	putchar('\n');

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

	return 0;
}