// The book only says inserting data into a sequence of data, not at the beginning or at the end.
// Given an n, then n ordered data, enter a number and insert it into the sequence.
// The original code of the book is as follows:

#include<bits/stdc++.h>
using namespace std;

int main(void) {
	int data[101], right[101];
	int i, n, t, len;
	//Read in existing numbers
	scanf("%d", &n);
	for (i = 1; i <= n; i++)
		scanf("%d", &data[i]);
	len = n;
	//Initialize arrays
	for (i = 1; i <= n; i++) {
		if (i != n)
			right[i] = i + 1;
		else
			right[i] = 0;
	}
	//Add a number directly to the end of the array data
	len++;
	scanf("%d", &data[len]);
	//Traverse from the head of the list
	t = 1;
	while (t != 0) {
		if (data[right[t]] > data[len]) {//If the value of the next node of the current node is greater than the current number to be inserted, insert the number into the middle
			right[len] = right[t];//The next node number of the new insertion number is equal to the next node number of the current node.
			right[t] = len;//The next node number of the current node is the number of new inserts.
			break;
		}
		t = right[t];//Move to the next position and start comparing
	}
	//All Numbers in the Output List
	t = 1;
	while (t != 0) {
		printf("%d ", data[t]);
		t = right[t];
	}
	
	return 0;
}

// Below is my change, the change is not decent already... It's a way of thinking. You can insert data at the beginning and at the end.

#include<bits/stdc++.h>
using namespace std;

int main(void) {
	int data[101], right[101];
	int i, n, t, len;
	int flag1 = 0, flag2 = 1;//flag1 is used to determine whether data is inserted in front of the first place, and flag2 is used to determine whether data is inserted in the last place.
	//Read in existing numbers
	scanf("%d", &n);
	for (i = 1; i <= n; i++)
		scanf("%d", &data[i]);
	len = n;
	//Initialize arrays
	for (i = 0; i <= n; i++) {
		if (i != n)
			right[i] = i + 1;
		else
			right[i] = -1;
	}
	//Add a number directly to the end of the array data
	len++;
	scanf("%d", &data[len]);
	//Traverse from the head of the list
	t = 0;
	while (t != -1) {
		if (data[right[t]] > data[len]) {//If the value of the next node of the current node is greater than the current number to be inserted, insert the number into the middle
			right[len] = right[t];//The next node number of the new insertion number is equal to the next node number of the current node.
			right[t] = len;//The next node number of the current node is the number of new inserts.

			//The special case is to insert a number before the first place.
			if (t == 0)//Because when t=0, right[0]=1 points to the first data, which corresponds to the next field of the header node.
				flag1 = 1;//But data[0] has no data, which is equivalent to the data domain of the header node.
			
			flag2 = 0;
			break;
		}
		t = right[t];//Move to the next position and start comparing
	}

	if (flag2 == 1) {//Explain that after traversing the list, no more than the number inserted can be found, so the number inserted can only be placed at the end of the list.
		right[len] = -1;//Put the number of inserts at the end, and the next field points to NULL, which is equivalent to -1 given here.
		right[len - 1] = len;//Let the previous next field point to itself
	}

	//All Numbers in the Output List
	if (flag1 == 1)//When inserting before the first number, for example, 23,558,9. This is the case when inserting 1
		t = 0;//The first data pointed to by the end node is needed, because the first data is output directly from the book, without considering the case of insertion in front of the first one. In this case, the first data is output after insertion.
	else//When inserting in the middle, for example, insert 2,358,9 into 6
		t = 1;//The output mode on the direct book is enough.

	while (t != -1) {
		if (flag1 == 1)//When inserting at the front, output the inserted element first
			printf("%d ", data[right[t]]);
		else
			printf("%d ", data[t]);

		if (flag1 == 1) {//After the insertion is finished, the normal operation of the book is returned, and the output starts from the first of the original data.
			t++;//So ++, because t=0.
			flag1 = 0;
		}
		else
			t = right[t];

	}

	return 0;
}