#include <stdio.h>
#include <stdlib.h>
typedef struct node ListNode ;
typedef struct node* PtrList ;
struct node
{
	int data ;
	struct node* next ;
} ;
PtrList CreateList( int N )
{
	int i ;
	int Data ;
	PtrList head ;
	PtrList PtrCurrent , PtrPrevious ;
	//建立一个表头为空结点的链表
	//链表的初始化
   
	PtrCurrent = ( PtrList )malloc( sizeof(ListNode) ) ;
	PtrCurrent->next = NULL ;
	head = PtrCurrent ;

	for( i=0 ; i<N ; i++ )
	{
		scanf("%d" , &Data) ;
		PtrPrevious = PtrCurrent ;
		PtrCurrent = ( PtrList )malloc( sizeof(ListNode) ) ;
		PtrCurrent->data = Data ;
		PtrPrevious->next = PtrCurrent ;
		PtrCurrent->next = NULL ;
	}
	return head ;
}
void  InsertList( PtrList List )
{
	int Data ;
	PtrList PrePosition ; //插入位置的前一个位置
    PtrList InsertNode ;
	scanf("%d" , &Data ) ;
	InsertNode = ( PtrList )malloc(sizeof(ListNode) ) ;
	InsertNode->data = Data ;
	InsertNode->next = NULL ;

	PrePosition = List ;
	while((InsertNode->data) > (PrePosition->next->data) && PrePosition->next!=NULL )
	{
		PrePosition = PrePosition->next ;
	}
	InsertNode->next = PrePosition->next;
	PrePosition = InsertNode ;

}
void PrintfList( PtrList head )
{
	PtrList p ;
	p = head->next ;
	while( p )
	{
		printf( "%d " , p->data ) ;
		p=p->next ;
	}
	printf("\n") ;
}
int main()
{
	int N ;
	PtrList List ;
	scanf("%d" , &N) ;

	List = CreateList( N ) ;
	PrintfList( List ) ;
 	InsertList( List ) ;
	PrintfList( List ) ;
}