Language: C++

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int,int> PP;

/*
    freopen("input","r",stdin);
    freopen("output","w",stdout);
*/

const int MAX_N = 1 << 18;

int n, dat[2 * MAX_N - 1][2];

void init(int n_) {
	n = 1;
	while (n < n_) n *= 2;
	for (int i = 0;i < 2 * n - 1;i++) {
		for (int j = 0;j < 2;j++) {
			dat[i][j] = INT_MAX;
		}
	}
}

void update(int k, int a, int t) {
	k += n - 1;
	dat[k][t] = a;
	while (k > 0) {
		k = (k - 1) / 2;
		dat[k][t] = min(dat[k * 2 + 1][t], dat[k * 2 + 2][t]);
	}
}

// [l, r)  query (0, N, 0, 0, n)
int query(int a, int b, int k, int l, int r, int t) {
	if (r <= a || b <= l) return INT_MAX;
	if (a <= l && r <= b) return dat[k][t];
	else {
		int vl = query(a, b, k * 2 + 1, l, (l + r) / 2, t);
		int vr = query(a, b, k * 2 + 2, (l + r) / 2, r, t);
		return min(vl, vr);
	}
}

int DP[200010];

int R[200010];

struct node {
	int l;
	int r;
	int num;
};

bool operator < (node a, node b) {
	return a.num > b.num;
}

int main() {
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    init(N + 10);
    for (int i = 0;i < N;i++) {
    	cin >> R[i];
    	DP[R[i]] = i;
    	update(i, R[i], i & 1);
    }
    priority_queue<node> P;
    node p;
    p.l = 0;
    p.r = N - 1;
    p.num = query(0, N, 0, 0, n, 0);
    P.push(p);
    vector<int> sol;
    while (P.size() > 0) {
    	p = P.top();
    	P.pop();
    	int s = p.l;
    	int b = p.r;
    	int idx = DP[p.num];
    	int ot = query(s, b + 1, 0, 0, n, 1 - (1 & s));
    	int idx2 = DP[ot];
    	sol.push_back(p.num);
    	sol.push_back(ot);
    	if (s < idx - 1) {
    		node q;
    		q.l = s;
    		q.r = idx - 1;
    		q.num = query(s, idx, 0, 0, n, (1 & s));
    		P.push(q);
    	}
    	if (idx + 1 < idx2 - 1) {
    		node q;
    		q.l = idx + 1;
    		q.r = idx2 - 1;
    		q.num = query(idx + 1, idx2, 0, 0, n, (1 & q.l));
    		P.push(q);
    	}
    	if (idx2 + 1 < b) {
    		node q;
    		q.l = idx2 + 1;
    		q.r = b;
    		q.num = query(idx2 + 1, b + 1, 0, 0, n, (1 & q.l));
    		P.push(q);
    	}
    }
    for (int i = 0;i < sol.size();i++) {
    	if (i != 0) cout << ' ';
    	cout << sol[i];
    }
    cout << endl;
    return 0;
}

Compiler output:
a.cc: In function 'void init(int)':
a.cc:42:37: error: 'INT_MAX' was not declared in this scope
   42 |                         dat[i][j] = INT_MAX;
      |                                     ^~~~~~~
a.cc:21:1: note: 'INT_MAX' is defined in header '<climits>'; this is probably fixable by adding '#include <climits>'
   20 | #include <utility>
  +++ |+#include <climits>
   21 | #include <vector>
a.cc: In function 'int query(int, int, int, int, int, int)':
a.cc:58:38: error: 'INT_MAX' was not declared in this scope
   58 |         if (r <= a || b <= l) return INT_MAX;
      |                                      ^~~~~~~
a.cc:58:38: note: 'INT_MAX' is defined in header '<climits>'; this is probably fixable by adding '#include <climits>'