#include <stdio.h>
#include <iostream>
#include <queue>
using namespace std;

int n;
int a[200005],aa[200005];
struct Tree
{
    int minn;
    int l,r;
    int num;
}treef[1000005],tree1[1000005],tree2[1000005];

struct Q
{
    int l,r;
    int num;
    int x;
    bool operator < (const Q &c) const
    	{
    	return x>c.x;
    	}
};
priority_queue<Q>q;

struct Ans
{
    int minn;
    int num;
};

void build(Tree tree[],int i,int l,int r)
{
    tree[i].l=l;
    tree[i].r=r;
    if (l==r)
        {
        tree[i].minn=a[l];
        tree[i].num=l;
        return ;
        }
    int mid=(l+r)/2;
    build(tree,i*2,l,mid);
    build(tree,i*2+1,mid+1,r);
    if (tree[i*2].minn<tree[i*2+1].minn)
        {
        tree[i].minn=tree[i*2].minn;
        tree[i].num=tree[i*2].num;
        }
    else
        {
        tree[i].minn=tree[i*2+1].minn;
        tree[i].num=tree[i*2+1].num;
        }
}

Ans Find(Tree tree[],int i,int l,int r)
{
    if (tree[i].l==l && tree[i].r==r)
       {
        Ans a;
        a.minn=tree[i].minn;
        a.num=tree[i].num;
        return a;
       }
    int mid=(tree[i].l+tree[i].r)/2;
    if (r<=mid) return Find(tree,i*2,l,r);
    if (l>=mid+1) return Find(tree,i*2+1,l,r);
    if (l<=mid && r>=mid+1)
       {
        Ans a,b;
        a=Find(tree,i*2,l,mid);
        b=Find(tree,i*2+1,mid+1,r);
        if (a.minn<b.minn) return a;
        else return b;
       }
}

void work()
{
    Q st,ex;
    st.x=tree1[1].minn;
    st.num=tree1[1].num;
    st.l=1;
    st.r=n;
    q.push(st);
    for (int i=1;i<=n/2;i++)
        {
        Q u;
        int minn;
        u=q.top();
        q.pop();
        printf ("%d ",u.x);
        Ans a,b;
        if (u.num%2==0)
           {
            a=Find(tree1,1,u.num+1,u.r);
            printf ("%d ",a.minn);
           }
        else
            {
            a=Find(tree2,1,u.num+1,u.r);
            printf ("%d ",a.minn);
            }
        if (u.num!=u.l)
            {
            ex.l=u.l;
            ex.r=u.num-1;
            if (u.l%2==1)
                {
                b=Find(tree1,1,ex.l,ex.r-1);
                ex.x=b.minn;
                ex.num=b.num;
                }
            else
                {
                b=Find(tree2,1,ex.l,ex.r-1);
                ex.x=b.minn;
                ex.num=b.num;
                }
            q.push(ex);
            }

        if (u.num+1!=a.num)
            {
            ex.l=u.num+1;
            ex.r=a.num-1;
            if ((u.num+1)%2==1)
                {
                b=Find(tree1,1,ex.l,ex.r-1);
                ex.x=b.minn;
                ex.num=b.num;
                }
            else
                {
                b=Find(tree2,1,ex.l,ex.r-1);
                ex.x=b.minn;
                ex.num=b.num;
                }
            q.push(ex);
            }

        if (a.num!=u.r)
            {
            ex.l=a.num+1;
            ex.r=u.r;
            if ((a.num+1)%2==1)
                {
                b=Find(tree1,1,ex.l,ex.r-1);
                ex.x=b.minn;
                ex.num=b.num;
                }
            else
                {
                b=Find(tree2,1,ex.l,ex.r-1);
                ex.x=b.minn;
                ex.num=b.num;
                }
            q.push(ex);
            }
        }
}

int main()
{
    scanf ("%d",&n);
    for (int i=1;i<=n;i++)
        scanf ("%d",&a[i]);
    for (int i=1;i<=n;i++)
        aa[i]=a[i];
    build(treef,1,1,n);
    for(int i=2;i<=n;i+=2)
        a[i]=1000000000;
    build(tree1,1,1,n);
    for (int i=1;i<=n;i++)
        a[i]=aa[i];
    for(int i=1;i<=n;i+=2)
        a[i]=1000000000;
    build(tree2,1,1,n);

    work();
}


Measured memory_bytes: 36340