#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define ignore ignore
#define pb emplace_back
#define mt make_tuple
#define gcd __gcd
#define bitcount(x)  __builtin_popcount(x)
#define bitcountll(x)  __builtin_popcountll(x)
// Input
#define in(a) scanf("%d",&a)
#define in2(a,b) scanf("%d%d",&a,&b)
#define in3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp(p) in2(p.F,p.S)
#define llin(a) cin >> a
#define inl(a) scanf("%lld",&a)
#define read(v,i,n) for(i=0;i<n;i++)in(v[i])
#define twod(mat,i,j,n,m) rep(i,n){rep(j,m)in(mat[i][j]);}
#define sc(ch) scanf("%c",&ch)
#define sstr(str) scanf("%s",str)
// Output
#define pr(a) printf("%d ",a)
#define pr2(a,b) printf("%d %d\n",a,b)
#define pr3(a,b,c) printf("%d %d %d\n",a,b,c)
#define prp(p) pr2(p.F,p.S)
#define out(a) printf("%d\n",a)
#define outl(a) printf("%lld\n",a)
#define llpr(a) cout << a << " "
#define llout(a) cout << a << "\n"
#define pinttwod(mat,i,j,n,m) rep(i,n){rep(j,m)pr(mat[i][j]);   lin;}
#define plltwod(mat,i,j,n,m)  rep(i,n){rep(j,m)llpr(mat[i][j]); lin;}
#define byes printf("YES\n")
#define bno printf("NO\n")
#define yes printf("Yes\n")
#define no printf("No\n")
#define lin printf("\n")
// Iterator
#define rep(i,n) for(i=0;i<n;++i)
#define fone(i,n) for(i=1;i<=n;++i)
#define rrep(i,n) for(i=n-1;i>=0;--i)
#define lp(i,a,b) for(i=a;i<b;++i)
#define rlp(i,a,b) for(i=a;i>=b;--i)
#define all(vec) vec.begin(),vec.end()
#define lower(v,k) lower_bound(v.begin(),v.end(),k)-v.begin()
#define upper(v,k) upper_bound(v.begin(),v.end(),k)-v.begin()
#define tf(mytuple) get<0>(mytuple)
#define ts(mytuple) get<1>(mytuple)
#define tt(mytuple) get<2>(mytuple)
// function
#define sz(x) x.size()
#define inrange(i,a,b) (i>=a && i<=b)
#define FLUSH fflush(stdout)
#define precision(x) cout << setprecision(x) << fixed
#define remax(a,b) a=max(a,b)
#define remin(a,b) a=min(a,b)
#define lchild(p) 2*p
#define rchild(p) 2*p+1
#define lseg l,m,2*p
#define rseg m+1,h,2*p+1
#define bhardo(mat,i,j,n,m,t) rep(i,n){rep(j,m)mat[i][j]=t;}
#define biton(mask,i)  (mask&(1<<i))
#define bitoff(mask,i) (!(mask&(1<<i)))
// Debug
#define dbg(v,i,n) for(i=0;i<n;i++)pr(v[i]); lin
#define ck printf("continue\n")
#define debug(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args)
{
	cerr << *it << " = " << a << "\n";
	err(++it, args...);
}
// Data Type
#define ll long long int
#define ii pair<int,int>
#define pli pair<ll,int>
#define triple tuple<int,int,int>
#define vi vector<int>
#define vii vector<pair<int,int> >
#define vvi vector<vector<int> >
#define viii vector<pair<pair<int,int>,int> >
#define vvii vector<vector<pair<int,int> > >
// Constant
const double PI = acos(-1);
const double eps = (1e-9);
const ll INF = 1e15;
const int M = (1e9)+7;
const int N = (1e5)+5;  // check the limit, man
int sp[2][N][20],po[20],ar[2*N];
int v[2][N],perm[2*N];
void pre()
{
    int i,k;
    ar[1]=0,k=1,po[0]=1;
    while(k<N)
    {
        for(i=k+1;i<2*k;i++)
            ar[i]=ar[k];
        ar[2*k]=1+ar[k],k*=2;
    }
    for(i=1;i<20;i++)
        po[i]=2*po[i-1];
        return ;
}
void up(int f,int j,int n)
{
    sp[f][j][0]=j;
    for(int k=1;k<20;k++)
    {
        if(j+po[k]<=n)
            sp[f][j][k]=v[f][sp[f][j][k-1]]<v[f][sp[f][j+po[k-1]][k-1]]?sp[f][j][k-1]:sp[f][j+po[k-1]][k-1];
    }
    return ;
}
int query(int f,int a,int b)
{
    int y,x=b-a+1;
    y=ar[x],x-=po[y];
    return v[f][sp[f][a][y]]<v[f][sp[f][a+x][y]]?sp[f][a][y]:sp[f][a+x][y];
}
ii call(int l,int r)
{
    int f=(l&1);
    int p=query(f,(l/2),(r-1)/2);
    int q=query(f^1,p+f,(r/2));
    return {lchild(p)+f,rchild(q)-f};
}
ii value(int l,int r)
{
    ii temp=call(l,r);
    return {perm[temp.F],perm[temp.S]};
}
void solve()
{
    int n,m,i,l,r,a,b;
    in(n);
    rep(i,n)
        in(a),v[i&1][i/2]=a,perm[i]=a;
    m=(n/2);
    pre();
    rrep(i,m)
        up(0,i,m),up(1,i,m);
    set<pair<ii,ii> > st;
    set<pair<ii,ii> > :: iterator itr;
    st.insert({value(0,n-1),{0,n-1}});
    vi ans;
    ii p1,temp;
    while(sz(st)>0)
    {
        itr=st.begin();
        tie(p1,temp)=(*itr);
        st.erase(itr);
        tie(l,r)=p1;
        ans.pb(l),ans.pb(r);
        tie(l,r)=temp;
        if(r==l+1)
            continue;
        tie(a,b)=call(l,r);
        if(a>l)
            st.insert({value(l,a-1),{l,a-1}});
        if(b>a+1)
            st.insert({value(a+1,b-1),{a+1,b-1}});
        if(r>b+1)
            st.insert({value(b+1,r),{b+1,r}});
    }
    dbg(ans,i,n);
}
int main()
{
    int t=1;
//    in(t);
    while(t--)
        solve();
}










Measured memory_bytes: 22772