#include <iostream>
#include <vector>
using namespace std;
template<typename T>

void Firstalg(T &x, int &a, int &b, int n){
	a=0;
	b=0;
	for(int i=0;i<n;i++){
		for(int j=0; j<n-i-1; j++){
			a+=1;
			if(x[j]>x[j+1]){
				swap(x[j],x[j+1]);
				b+=1;
			}
		}
	}
}

template<typename T>
void Secondalg(T &x, int &a, int &b, int n){
	a=0;
	b=0;
	for(int i=1; i<n; i++){
		int key = x[i];
		int j=i-1;
		while(j>=0){
			a+=1;
			if(x[j]>key){
			x[j+1]=x[j];
			b+=1;
			j--;
			}else{break;}
		}
		x[j+1]=key;
	}
}

int main() {
	int n, sort, comp;
	cin>>n;
	int *x = new int[n];
	for (int i=0; i<n; i++){
		cin>>x[i];
	};
	
	for (int i=0; i<n; i++){
		cout<<x[i]<<" ";
	};
	cout<<endl;
	//Для векторів
	vector<int> myVector ={8, 9 ,4 ,0};
	Firstalg(myVector,sort,comp,4);
	for(int i: myVector)cout<<i<<" ";
	cout<<"\nКількість порівнянь "<<sort<<endl<<"Кількість перестановок "<<comp;
	Secondalg(myVector,sort,comp,4);
	for(int i: myVector)cout<<i<<" ";
	cout<<"\nКількість порівнянь "<<sort<<endl<<"Кількість перестановок "<<comp;
	
	
/*	Secondalg(x,sort,comp,n);
	for (int i=0; i<n; i++){
		cout<<x[i]<<" ";
	};
	cout<<endl;
	cout<<"Кількість порівнянь "<<sort<<endl<<"Кількість перестановок "<<comp;
	
	Firstalg(x,sort,comp,n);
	for (int i=0; i<n; i++){
		cout<<x[i]<<" ";
	};
	cout<<endl;
	cout<<"Кількість порівнянь "<<sort<<endl<<"Кількість перестановок "<<comp;
	
	//First Algoritm
	int a=0;
	int b=0;
	for(int i=0;i<n;i++){
		for(int j=0; j<n-i-1; j++){
			a+=1;
			if(x[j]>x[j+1]){
				swap(x[j],x[j+1]);
				b+=1;
			}
		}
	}
	
	for (int i=0; i<n; i++){
		cout<<x[i]<<" ";
	};
	cout<<endl;
	cout<<"Кількість порівнянь "<<a<<endl<<"Кількість перестановок "<<b;
	
	//Second
	int a=0;
	int b=0;
	for(int i=1; i<n; i++){
		int key = x[i];
		int j=i-1;
		while(j>=0){
			a+=1;
			if(x[j]>key){
			x[j+1]=x[j];
			b+=1;
			j--;
			}else{break;}
		}
		x[j+1]=key;
	}
	
	for (int i=0; i<n; i++){
		cout<<x[i]<<" ";
	};
	cout<<endl;
	cout<<"Кількість порівнянь "<<a<<endl<<"Кількість перестановок "<<b;*/

}