//嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎

#include<iostream>
using namespace std;

class Array
{
private:
int size;
int n;
int *a;
public:
Array(int set_n)
{
size=10000;
a=new int[size];
n=set_n;
}

void set_array()
{
for(int i=0;i<n;i++)
{
cin>>a[i];
}
}

void output()
{
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}

int i_find_index(int x)
{
for(int i=0;i<n;i++)
if(a[i]==x)
return i;
return -1;
}

/*
错误数值
5
1 2 3 4 5
30
30 1 2 3 4 5
*/

void sort_insert(int x)
{
n=n+1;//提前增大原数组的空间
int flag=0;
if(x>=a[n-2])
{
a[n-1]=x;
return;
}
for(int i=0;i<n;i++)
{
if(a[i]>x)
{
flag=i;//flag为第一个大于x的值的下标
break;//别忘了跳出循环
}
}

for(int i=n-1;i>flag;i--)
{
a[i]=a[i-1];
}
a[flag]=x;
}

};

int main()
{
int n;
int x;
cin>>n;
Array arr(n);
arr.set_array();
cin>>x;
arr.sort_insert(x);
//cout<<arr.i_find_index(x)<<endl;
arr.output();
return 0;
}

#include<iostream>
using namespace std;

class Array
{
private:
    int size;
    int n;
    int *a;
public:
    Array(int set_n)
    {
        size=10000;
        a=new int[size];
        n=set_n;
    }
    
    void set_array()
    {
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
        }
    }
    
    void output()
    {
        for(int i=0;i<n;i++)
        {
            cout<<a[i]<<" ";
        }
        cout<<endl;
    }
    
    int i_find_index(int x)
    {
        for(int i=0;i<n;i++)
            if(a[i]==x)
                return i;
        return -1;
    }

    /*
    错误数值
    5
    1 2 3 4 5
    30
    30 1 2 3 4 5
    */
    
    void sort_insert(int x)
    {
        n=n+1;//提前增大原数组的空间
        int flag=0;
        if(x>=a[n-2])
            {
                a[n-1]=x;
                return;
            }
        for(int i=0;i<n;i++)
        {
            if(a[i]>x)
            {
                flag=i;//flag为第一个大于x的值的下标
                break;//别忘了跳出循环
            }
        }
        
        for(int i=n-1;i>flag;i--)
        {
            a[i]=a[i-1];
        }
        a[flag]=x;
    }
        
        
    
};

int main()
{
    int n;
    int x;
    cin>>n;
    Array arr(n);
    arr.set_array();
    cin>>x;
    arr.sort_insert(x);
    //cout<<arr.i_find_index(x)<<endl;
    arr.output();
    
    system("pause");
    return 0;
}