# include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const double PI = acos(-1);
template<class T>constexpr T INF() { return ::std::numeric_limits<T>::max(); }
template<class T>constexpr T HINF() { return INF<T>() / 2; }
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
template<typename T>vector<T> make_v(size_t a){ return vector<T>(a); }
template<typename T,typename... Ts>auto make_v(size_t a, Ts... ts){ return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); }
template<typename T,typename V>typename enable_if<is_class<T>::value==0>::type fill_v(T &t, const V &v){ t = v; }
template<typename T,typename V>typename enable_if<is_class<T>::value!=0>::type fill_v(T &t, const V &v){ for(auto &e : t) fill_v(e, v); }
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
int d_sum(LL n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; }
int d_cnt(LL n) { int ret = 0; while (n > 0) { ret++; n /= 10; }return ret; }
LL gcd(LL a, LL b) { if (b == 0)return a; return gcd(b, a%b); };
LL lcm(LL a, LL b) { LL g = gcd(a, b); return a / g*b; };
# define ALL(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define UNIQUE(wpwpw)        sort(ALL((wpwpw)));(wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(ALL((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(ALL((rprpr)),(rprpr).begin(),TU<char>)
# define FOR(i,tptpt,ypypy)   for(LL i=(tptpt);i<(ypypy);i++)
# define REP(i,upupu)         FOR(i,0,upupu)
# define INIT                 std::ios::sync_with_stdio(false);std::cin.tie(0)

struct SegmentTree {
private:
    int n;
    vector<int> node;
public:
    SegmentTree(vector<int> v) {
        int sz = v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1, INF<int>());
        for(int i=0; i<sz; i++) node[i+n-1] = v[i];
        for(int i=n-2; i>=0; i--) node[i] = min(node[2*i+1], node[2*i+2]);
    }
 
    void update(int x, int val) {
        x += (n - 1);
        node[x] = val;
        while(x > 0) {
            x = (x - 1) / 2;
            node[x] = min(node[2*x+1], node[2*x+2]);
        }
    }
    //[a,b)の最小値を求める
    int getmin(int a, int b, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        if(r <= a || b <= l) return INF<int>();
        if(a <= l && r <= b) return node[k];
 
        int vl = getmin(a, b, 2*k+1, l, (l+r)/2);
        int vr = getmin(a, b, 2*k+2, (l+r)/2, r);
        return min(vl, vr);
    }
};

int n;
int p[202020];
vector<int>ans;
map<int, int> mp;

int main(){
	cin >> n;
	vector<int> e(n), o(n);
	REP(i, n){
		cin >> p[i];
		mp[p[i]] = i;
		if(i % 2){
			o[i] = p[i];
			e[i] = INF<int>();
		}
		else {
			e[i] = p[i];
			o[i] = INF<int>();
		}
	}
	SegmentTree even(e), odd(o);
	priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
	pq.push(make_pair(even.getmin(0, n - 1),make_pair(0, n)));
	REP(i, n){
		auto cur = pq.top();
		//cout << cur.first << " " << cur.second.first << " " << cur.second.second << endl;
		pq.pop();
		int num = -1;
		if(mp[cur.first]%2){
			ans.emplace_back(cur.first);
			odd.update(mp[cur.first], INF<int>());
			num = even.getmin(mp[cur.first], cur.second.second);
			ans.emplace_back(num);
			odd.update(mp[num], INF<int>());
		}else{
			ans.emplace_back(cur.first);
			even.update(mp[cur.first], INF<int>());
			num = odd.getmin(mp[cur.first], cur.second.second);
			ans.emplace_back(num);
			even.update(mp[num], INF<int>());
		}
		if(cur.second.first != mp[cur.first]){
			if((cur.second.first)%2)pq.push(make_pair(odd.getmin(cur.second.first, mp[cur.first] - 1), make_pair(cur.second.first, mp[cur.first])));
			else pq.push(make_pair(even.getmin(cur.second.first, mp[cur.first] - 1), make_pair(cur.second.first, mp[cur.first])));
		}
		if(mp[cur.first] != mp[num] - 1){
			if((mp[cur.first] + 1)%2)pq.push(make_pair(odd.getmin(mp[cur.first] + 1, mp[num] - 1), make_pair(mp[cur.first] + 1, mp[num])));
			else pq.push(make_pair(even.getmin(mp[cur.first] + 1, mp[num] - 1), make_pair(mp[cur.first] + 1, mp[num])));
		}
		if(cur.second.second != mp[num]){
			if((mp[num] + 1)%2)pq.push(make_pair(odd.getmin(mp[num] + 1, cur.second.second - 1), make_pair(mp[num] + 1, cur.second.second)));
			else pq.push(make_pair(even.getmin(mp[num] + 1, cur.second.second - 1), make_pair(mp[num] + 1, cur.second.second)));
		}
	}
	REP(i, n){
		if(i)cout << " ";
		cout << ans[i];
	}
	cout << endl;
}

Measured memory_bytes: 23788