/*
    Look at me!
    Look at me!
    Look at how large the monster inside me has become!
*/

#include<fstream>
#include<cstdio>
#include<map>
#include<set>
#define FIT(a,b) for(vector<int >::iterator a=b.begin();a!=b.end();a++)
#define FITP(a,b) for(vector<pair<int,int> >::iterator a=b.begin();a!=b.end();a++)
#define RIT(a,b) for(vector<int>::reverse_iterator a=b.end();a!=b.begin();++a)
#include<stack>
#define ROF(a,b,c) for(int a=b;a>=c;--a)
#include<vector>
#include<algorithm>
#define FOR(a,b,c) for(int a=b;a<=c;++a)
#define REP(a,b) for(register int a=0;a<b;++a)
#include<cstring>
#include<bitset>
#include<cmath>
#include<iomanip>
#define f cin
#define g cout
#include<queue>
#define INF 0x3f3f3f3f
#define debug cerr<<"OK";
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define eps 1.e-9
#define BUFMAX 10100100
#define N 100100
#define BM 100100
#define mod 1000000007
#define inf (1<<30)
using namespace std;
/*int dx[]={0,0,0,1,-1};
int dy[]={0,1,-1,0,0};*/
ifstream f("invsort.in");
ofstream g("invsort.out");

int n;
struct Tr
{
    Tr *l,*r;
    int pr,mi,e,cnt,val;
    Tr(int _key,int _val)
    {
        cnt=_key;
        val=_val;
        pr=rand();
        mi=_val;
        l=r=NULL;
        e=0;
    }
};
#define T Tr*
T R;
int mi(T t)
{
    if(!t)
        return (1<<30);
    return t->mi;
}

int cnt(T t)
{
    if(!t)
        return 0;
    return t->cnt;
}
void upd(T &t)
{
    if(!t)
        return ;
    t->cnt=cnt(t->l)+cnt(t->r)+1;
    t->mi=min(mi(t->l),mi(t->r));
    t->mi=min(t->mi,t->val);
}
void push(T &t)
{
    if(t&&t->e)
    {
        t->e=0;
        swap(t->l,t->r);
        if(t->l)
            t->l->e^=1;
        if(t->r)
            t->r->e^=1;
    }
}
void merge(T &t,T l,T r)
{
    if(!l||!r)
    {
        t=l?l:r;
        upd(t);
        return ;
    }
    push(l); push(r);
    if(l->pr>r->pr)
        merge(l->r,l->r,r),t=l;
    else
        merge(r->l,l,r->l),t=r;
    upd(t);
}
void split(T t,T &l,T &r,int key,int cur)
{
    if(!t)
    {
        l=r=t;
        return;
    }
    push(t);
    int cur_key=cur+cnt(t->l)+1;
    if(key<=cur_key)
        split(t->l,l,t->l,key,cur),r=t;
    else
        split(t->r,t->r,r,key,cur_key),l=t;
    upd(t);
}
void insert(T &t,T it,int cur)
{
    if(!t)
    {
        t=it;
        upd(t);
        return;
    }
    push(t);
    int cur_key=cnt(t->l)+cur+1;
    if(it->pr>t->pr)
        split(t,it->l,it->r,it->cnt,cur),t=it;
    else
    if(it->cnt<cur_key)
        insert(t->l,it,cur);
    else
    if(it->cnt>cur_key)
        insert(t->r,it,cur_key);
    else
    {
        if(rand()%2)
            insert(t->l,it,cur);
        else
            insert(t->r,it,cur_key);
    }
    upd(t);
}
void erase(T &t,int key,int cur)
{
    if(!t)
        return;
    push(t);
    int cur_key=cur+cnt(t->l)+1;
    if(key==cur_key)
        merge(t,t->l,t->r);
    else
    if(key<cur_key)
        erase(t->l,key,cur);
    else
        erase(t->r,key,cur_key);
    upd(t);
}
int find(T it,int cur)
{
    push(it);
    int cur_key=cur+cnt(it->l)+1;
    if(it->val==it->mi)
        return cur_key;
    if(it->mi==mi(it->l))
        return find(it->l,cur);
    else
        return find(it->r,cur_key);
}
void reverse(int p)
{
    Tr *t1;
    split(R,R,t1,p+1,0);
    R->e^=1;
    merge(R,R,t1);
}
int main ()
{
    f>>n;
    FOR(i,1,n)
    {
        int x;
        f>>x;
        T it=new Tr(i,x);
        insert(R,it,0);
    }
    FOR(i,1,n)
    {
        int x=find(R,0);
        if(x==1)
        {
            erase(R,1,0);
            continue;
        }
        reverse(x);
        g<<i<<" "<<x+i-1<<"\n";
        erase(R,1,0);
    }
    return 0;
}