#include <bits/stdc++.h>

using namespace std;
/*
8
2 3 5 8 7 6 4 1
*/
int main()
{
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++)
        cin>>a.at(i);

    vector<int> vege;
    //a vector vegerol levesszuk a csokkeno reszt
    int index=n-1;   //2 3 5 4 1

    while(a.at(index-1)>a.at(index))
    {
        vege.push_back(a.at(index));
        index--;
    }
    vege.push_back(a.at(index));

    for(int x:vege)
        cout<<x<<" ";
/*
    sort(vege.begin(),vege.end(),greater<int>());
    cout<<endl;
    for(int x:vege)
        cout<<x<<" ";
*/
    cout<<"cserelni kell a "<<a.at(index-1)<<endl;
    int j=0;
    while(a.at(index-1)>vege.at(j))
        j++;

            int temp=vege.at(j);
            vege.at(j)=a.at(index-1);
            a.at(index-1)=temp;

    cout<<endl;
    for(int x:a)
      cout<<x<<" ";
    cout<<endl;
    for (int x:vege)
        cout<<x<<" ";
    vector<int> kicsik, nagyok;
    for(int x:vege)
    {
        if(x>a.at(index-1))
            nagyok.push_back(x);
        else
            kicsik.push_back(x);
    }
    cout<<endl;
    for(int x:nagyok)
      cout<<x<<" ";
    cout<<endl;
    for(int x:kicsik)
      cout<<x<<" ";
    int hol=kicsik.size()-1;
    for (int i=index;i<index+kicsik.size();i++)
    {
        a.at(i)=kicsik.at(hol);
        hol--;
    }
    index+=kicsik.size();
    hol=0;
    for(int i=index;i<n;i++)
    {
        a.at(i)=nagyok.at(hol);
        hol++;
    }
    cout<<endl;
    for(int x:a)
        cout<<x<<" ";












    //cout << "Hello world!" << endl;
    return 0;
}