#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <set>
#define N 200010
#define inf 2147483640
using namespace std;
struct P
{
    int Min, Max;
}c[4 * N];
int a[N], ans[N], pos[N];
int lz[4 * N];
void Push_up(int node)
{
    c[node].Min = min(c[node << 1].Min, c[node << 1 | 1].Min);
    c[node].Max = max(c[node << 1].Max, c[node << 1 | 1].Max);
}
void Push_down(int node)
{
    if(lz[node])
    {
        swap(c[node << 1].Max, c[node << 1].Min);
        c[node << 1].Max *= -1;
        c[node << 1].Min *= -1;
        swap(c[node << 1 | 1].Max, c[node << 1 | 1].Min);
        c[node << 1 | 1].Max *= -1;
        c[node << 1 | 1].Min *= -1;
        lz[node << 1] ^= 1;
        lz[node << 1 | 1] ^= 1;
        lz[node] = 0;
    }
}
void build(int node, int l, int r)
{
    if(l == r)
    {
        if(a[l] > 0)
        {
            c[node].Min = a[l];
            c[node].Max = -inf;
        }else
        {
            c[node].Min = inf;
            c[node].Max = a[l];
        }
        return ;
    }
    int mid = (l + r) / 2;
    build(node << 1, l, mid);
    build(node << 1 | 1, mid + 1, r);
    Push_up(node);
}
void update(int node, int l, int r, int left, int right)
{
    if(l >= left && r <= right)
    {
        lz[node] ^= 1;
        swap(c[node].Max, c[node].Min);
        c[node].Max *= -1;
        c[node].Min *= -1;
        return ;
    }
    Push_down(node);
    int mid = (l + r) / 2;
    if(mid >= left)
        update(node << 1, l, mid, left, right);
    if(mid < right)
        update(node << 1 | 1, mid + 1, r, left, right);
    Push_up(node);
}
P query(int node, int l, int r, int left, int right)
{
    if(l >= left && r <= right)
    {
        return c[node];
    }
    P p, p1, p2;
    p.Max = p1.Max = p2.Max = -inf;
    p.Min = p1.Min = p2.Min = inf;
    Push_down(node);
    int mid = (l + r) / 2;
    if(mid >= left)
        p1 = query(node << 1, l, mid, left, right);
    if(mid < right)
        p2 = query(node << 1 | 1, mid + 1, r, left, right);
    p.Max = max(p1.Max, p2.Max);
    p.Min = min(p1.Min, p2.Min);
    //Push_up(node);
    return p;
}
void update2(int node, int l, int r, int d)
{
    if(l == r)
    {
        c[node].Max = -inf;
        c[node].Min = inf;
        return ;
    }
    Push_down(node);
    int mid = (l + r) / 2;
    if(mid >= d)
        update2(node << 1, l, mid, d);
    else
        update2(node << 1 | 1, mid + 1, r, d);
    Push_up(node);
}
set<int>S;
set<int>::iterator q;
int main()
{
    int n, x, i, ee;
    P p, p1;
    scanf("%d", &n);
    for(i = 1; i <= n; ++i)
    {
        scanf("%d", &x);
        pos[x] = i;
        if(i % 2 == 1)
            a[i] = x;
        else
            a[i] = -x;
    }
    build(1, 1, n);
    int cnt = 0;
    for(int cc = 1; cc <= n / 2; ++cc)
    {
        p = query(1, 1, n, 1, n);
        ans[++cnt] = p.Min;
        S.insert(pos[ans[cnt]]);
        update2(1, 1, n, pos[ans[cnt]]);
        q = S.upper_bound(pos[ans[cnt]]);
        if(q == S.end())
            ee = n;
        else
            ee = *q;
        p = query(1, 1, n, pos[ans[cnt]] + 1, ee);
        ans[++cnt] = -p.Max;
        S.insert(pos[ans[cnt]]);
        update(1, 1, n, pos[ans[cnt - 1]], pos[ans[cnt]]);
        update2(1, 1, n, pos[ans[cnt]]);
    }
    for(i = 1; i <= n; ++i)
    {
        printf("%d", ans[i]);
        if(i == n)
            printf("\n");
        else
            printf(" ");
    }
    return 0;
}
/*
8
8 7 6 5 4 3 2 1
*/


Measured memory_bytes: 21120