#include<iostream>
using namespace std;
void sets(int* array, int size);
int main() {
	int size = 0;
	cout << "Enter size of the array" << endl;
	cin >> size;
	int* array = new int[size];
	cout << "Enter elements of the array " << endl;
	for (int i = 0; i < size; i++)
		cin >> array[i];
	sets(array, size);
	return 0;
}
void sets(int* array, int size) {
	int* newarray1 = nullptr;
	int* newarray2 = nullptr;
	int median = size / 2;
	if (size % 2 == 0) {
		 newarray1 = new int[median];
		 newarray2 = new int[median];
	}
	else if (size % 2 != 0)
	{
		 newarray1 = new int[median+1];
		 newarray2 = new int[median];
	}
	//applying the insertion sort to sort the elements in ascending order
	int key;
	for (int i = 1; i < size; i++)
	{
		key = array[i];
		int j = i - 1;
		while (j>=0&&array[j]>key)
		{
			array[j + 1] = array[j];
			j = j - 1;
		}
		array[j + 1] = key;
		
	}
	for (int i = 0; i < size; i++)
				cout << array[i] << "  ";
	
	if (size % 2 == 0) {
		for (int i = 0; i < median; i++)
		{
			newarray1[i] = array[i];
		}
		for (int i = median; i < size; i++)

			newarray2[i-median] = array[i];
	}

	if (size % 2 != 0)
	{
		for (int i = 0; i < median + 1; i++)
			newarray1[i] = array[i];

		for (int j = median + 1; j < size; j++)
			newarray2[j - median + 1] = array[j];
	}

	cout << endl;
	if (size % 2 == 0) {
		for (int i = 0; i < median; i++)
		{
			cout << newarray1[i] <<  "  " << endl;
		}
		cout << endl;
		for (int i = median; i < size; i++)

			cout << newarray2[i - median] <<"  " << endl;

		cout << endl;
	}

	if (size % 2 != 0)
	{
		for (int i = 0; i < median + 1; i++)
			cout << newarray1[i] << "  "  << "  " << endl;
		cout << endl;
		for (int j = median + 1; j < size; j++)
			cout << newarray2[j - median + 1] << "   "  << endl;
	}
	


}