#include <cmath>
#include <math.h>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define maxn 1000030
using namespace std;
inline void read(int &x) {
    char ch;
    bool flag = false;
    for (ch = getchar(); !isdigit(ch); ch = getchar())if (ch == '-') flag = true;
    for (x = 0; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
    x = flag ? -x : x;
}
inline void write(int x) {
    static const int maxlen = 100;
    static char s[maxlen];
    if (x < 0) {   putchar('-'); x = -x;}
    if (!x) { putchar('0'); return; }
    int len = 0; for (; x; x /= 10) s[len++] = x % 10 + '0';
    for (int i = len - 1; i >= 0; --i) putchar(s[i]);
}


int n,m;
int a[maxn];
int ans[maxn];

int lim,MIN[maxn][2],MINI[maxn][2];
int belong [maxn];
int l[maxn],r[maxn],cnt;
int siz[maxn];
int stop[maxn];

void prepare(){
lim=sqrt(n);
if (lim%2==1)
    lim++;
for (int i=1;i<=n;i+=lim)
    {
        ++cnt;
        l[ cnt ] =i;
        r[ cnt ] =i+lim-1;
    }
r[cnt]=n;
for (int i=1;i<=cnt;i++)
    siz[i]=r[i]-l[i]+1;
for (int i=1;i<=cnt;i++)
    {
        stop[i]=n+2;
        for (int j=l[i];j<=r[i];j++)
            belong[j]=i;
        MIN[i][0]=n+2;
        for (int j=l[i]+1;j<=r[i];j+=2)
            if (MIN[i][0]>a[j])
                {
                    MIN[i][0]=a[j];
                    MINI[i][0]=j;
                }
        MIN[i][1]=n+2;
        for (int j=l[i];j<=r[i];j+=2)
            if (MIN[i][1]>a[j])
                {
                    MIN[i][1]=a[j];
                    MINI[i][1]=j;
                }
    }
}


int tmp[2];
int tmpi[2];

void update(int x){
int now=0;
MIN[x][0]=n+2;
MIN[x][1]=n+2;
for (int i=l[x];i<=r[x];i++)
    {
        while ( (i<=r[x]) &&(a[i]==n+2) )
            i++;
        if (i>r[x])
            break;
        now++;
        if ( MIN[ x ] [ now%2 ]> a[i] )
            {
                MIN[ x ] [ now%2 ]=a[i];
                MINI [ x ][ now%2 ]=i;
            }
    }
}


void Delete(int x,int y){
stop[ belong [x] ]=min( stop[ belong [x] ],x);  stop[ belong [y] ]=min( stop[ belong [y] ],y);
a[x]=n+2; a[y]=n+2;
siz[ belong [x] ]--; siz[ belong [y] ]--;
update( belong [x] );   update( belong [y] );
}

int sum=0;


void watch(){
puts("\n");
for (int i=1;i<=cnt;i++)
    {
        printf("block: %d\n",i);
        for (int j=l[i];j<=r[i];j++)
            printf("%d ",a[j]);
        puts("");
        printf("MIN[0]= %d  MIN[1]=%d\n",MIN[i][0],MIN[i][1]);
        printf("size = %d\n",siz[i]);
    }
}

int main(){
    read(n);
    for (int i=1;i<=n;i++)
        read(a[i]);
    prepare();
    //watch();
    for (int i=1;i<=n/2;i++)
    {
        tmp[0]=n+2;
        tmp[1]=n+2;
        sum=0;
        for(int j=1;j<=cnt;j++)
        {
            if (MIN[j][ (1+sum%2)%2 ]<tmp[1])
            {
                //printf("tmp[0]  ??? %d\n",MIN[j][1+sum%2]);
                tmp[1]=MIN[j][ (1+sum%2)%2 ];
                tmpi[1]=MINI[j][ (1+sum%2)%2 ];
            }
            sum+=siz[j];
        }
        int now=0;
        int op=1;
        for (int j=tmpi[1];j<=r[ belong [tmpi [1] ] ];j++)
        {
            if ( a[ j ]==n+2 )
            {
                op=0;
                break;
            }
            now++;
            if (now%2==0)
                {
                    if (tmp[0]> a[j])
                    {
                        tmp[0]=a[j];
                        tmpi[0]=j;
                    }
                }
        }
        sum=0;
        for (int j=1;j<=belong [ tmpi[1] ];j++)
            sum+=siz[j];
        if( op )
        for(int j=belong [ tmpi[1] ]+1;j<=cnt;j++)
        {
            //printf(" pd %d\n",j);
            if (  stop[j]!=n+2)
                {
                    int now=sum;
                    for (int k=l[j];k<=r[j];k++)
                        {
                            if (a[k]==n+2)
                                break;
                            sum++;
                            if (sum%2==0)
                            if (a[k]<tmp[0])
                                {
                                    tmp[0]=a[k];
                                    tmpi[0]=k;
                                }
                        }
                    break;
                }
            //printf("tmp[0]  ??? %d\n",MIN[j][sum%2]);
            if (MIN[j][ sum%2 ]<tmp[0])
            {
                tmp[0]=MIN[j][ sum%2 ];
                tmpi[0]=MINI[j][ sum%2 ];
            }
            sum+=siz[ j ];
        }
        ans[i*2-1]=tmp[1];
        ans[i*2]=tmp[0];
        Delete(  tmpi[0], tmpi[1] );
        //watch();
    }

    for (int i=1;i<n;i++)
        printf("%d ",ans[i]);
    printf("%d\n",ans[n]);
    return 0;
}


Measured memory_bytes: 19968