#include <iostream>
#include <fstream>

using namespace std;

int v[500001], aux[500001];

void mergSort(int s, int f)
{
    if(f-s==1)
    {
        if( v[s] > v[f] )
            swap(v[s],v[f]);
    }
    if(f-s>=2)
    {
        int m=(s+f)/2;
        mergSort(s,m);
        mergSort(m+1,f);
        cout<<s<<" "<<f<<endl;
        for(int i=s;i<=f;i++)
            cout<<v[i]<<" ";
        cout<<endl;
        int k = s, i ,j;
        for(i=s, j=m+1; i<=m && j<=f; )
            if(v[i] < v[j])
            {
                aux[k] = v[i];
                k++;
                i++;
            }
            else
            {
                aux[k] = v[j];
                k++;
                j++;
            }
        for(;i<=m;i++)
            aux[k++] = v[i];
        for(;j<=f;j++)
            aux[k++] = v[j];

        for(int i=s;i<=f;i++)
            v[i]=aux[i];
        cout<<s<<" "<<f<<endl;
        for(int i=s;i<=f;i++)
            cout<<v[i]<<" ";
        cout<<endl;
    }
}

int main()
{
    ifstream f("algsort.in");
    ofstream g("algsort.out");
    int n;
    f>>n;
    //cout<<n;
    for (int i=1;i<=n;i++)
        f>>v[i];
    mergSort(1,n);
    for (int i=1;i<=n;i++)
        g<<v[i]<<" ";
    g.close();
    f.close();
    return 0;
}