#include <iostream>
#include <ctime>
#include <vector>
#include <algorithm>

using namespace std;

int n;
vector<int > v;
vector<int > aux;

void read()
{
	srand(time(0));
	cout<<"n=";cin>>n;
	v.resize(n+1);
	aux.resize(n+1);
	for (int i=1; i<=n; ++i)	v[i]=rand();
}

void merge_sort(int left, int right)
{
	if (left >= right)
		return;

	int m=(left+right)/2;
	
	merge_sort(left, m);
	merge_sort(m+1, right);

	int i,j,nr=0;

	for (i=left, j=m+1; i<=m && j<=right ; )
		if (v[i] > v[j])
			aux[++nr]=v[i++];
		else
			aux[++nr]=v[j++];

	for ( ; i<=m ; ++i)
		aux[++nr]=v[i];

	for ( ; j<=right ; ++j)
		aux[++nr]=v[j];

	for (j=1, i=left; j<=nr; ++j, ++i)
		v[i]=aux[j];
}

bool verificare()
{
	for (int i=2; i<=n; ++i)
		if (v[i] > v[i-1])
			return 0;
	return 1;
}

int main()
{
	read();
	for (int i=1; i<=n; ++i)
		cout<<v[i]<<" ";
	cout<<endl<<endl;
	merge_sort(1, n);

	if (verificare())
		cout<<"SUNT SORTATE!";
	else
		cout<<"NU SUNT SORTATE!";

	cout<<endl<<endl;
	for (int i=1; i<=n; ++i)
		cout<<v[i]<<" ";

	return 0;
}