Language: C++

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define y0 yy
#define y1 Yy
#define yn YY
#include <assert.h>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int inf = 0x3f3f3f3f;

struct Treap {
	struct Node {
		int id, w, v, nm, nmid, nl, nr;
		Node* l, * r;
		Node(int id_, int v_, int w_): id(id_), v(v_), w(w_), nm(v_), nmid(id_), nl(id_), nr(id_), l(NULL), r(NULL) {}

		void update() {
			nm = v, nmid = nl = nr = id;
			if (l != NULL) {
				l->update();
				if (nm > l->nm) nm = l->nm, nmid = l->nmid;
				nl = min(nl, l->nl);
			}
			if (r != NULL) {
				r->update();
				if (nm > r->nm) nm = r->nm, nmid = r->nmid;
				nr = max(nr, r->nr);
			}
		}

		void show(vector<int>& res) {
			if (l != NULL) l->show(res);
			res.push_back(id);
			if (r != NULL) r->show(res);
		}
	};

	int randInt() const { return rand() * (RAND_MAX + 1) + rand(); }
	static const int infw = (RAND_MAX + 1) * (RAND_MAX + 1);

	Node* rt;

	Treap(): rt(NULL) { randInt(); }
	Treap(Node* rt_): rt(rt_) { randInt(); }

	Node* rotateL(Node* curr) {
		Node* res = curr->r;
		curr->r = res->l;
		res->l = curr;
		curr->update();
		res->update();
		return res;
	}

	Node* rotateR(Node* curr) {
		Node* res = curr->l;
		curr->l = res->r;
		res->r = curr;

		curr->update();
		res->update();
		return res;
	}

	Node* addNode(Node* curr, int id, int v, int w) {
		if (curr == NULL) return new Node(id, v, w);
		Node* res;
		if (id < curr->id) {
			curr->l = addNode(curr->l, id, v, w);
			if (curr->w < curr->l->w) res = rotateR(curr); else res = curr;
		} else {
			curr->r = addNode(curr->r, id, v, w);
			if (curr->w < curr->r->w) res = rotateL(curr); else res = curr;
		}
		res->update();
		return res;
	}

	Node* deleteNode(Node* curr, int id) {
		assert(curr != NULL);
		if (id < curr->id) curr->l = deleteNode(curr->l, id);
		else if (id > curr->id) curr->r = deleteNode(curr->r, id);
		else {
			Node* res = NULL;
			if (curr->l != NULL && curr->r != NULL) {
				if (curr->l->w > curr->r->w) {
					res = rotateR(curr);
					res->r = deleteNode(res->r, id);
				} else {
					res = rotateL(curr);
					res->l = deleteNode(res->l, id);
				}
				res->update();
			} else if (curr->l != NULL) {
				res = curr->l;
				delete curr;
			} else if (curr->r != NULL) {
				res = curr->r;
				delete curr;
			} else delete curr;
			return res;
		}
		curr->update();
		return curr;
	}

	void split(Node* curr, Node*& l, Node*& r, int sid) {
		// LEQUAL sid => l
		curr = addNode(curr, sid, 0, infw);
		assert(curr->id == sid);
		l = curr->l;
		r = curr->r;
		delete curr;
	}

	Node* merge(Node* l, Node* r, int sid) {
		// l => LEQUAL sid
		Node* res = new Node(sid, 0, infw);
		res->l = l, res->r = r;
		return deleteNode(res, sid);
	}

	pair<int, int> minInRange(Node* curr, int l, int r) const {
		// Range GEQUAL l, LEQUAL r
		if (curr == NULL) return make_pair(inf, -1);
		if (curr->nl >= l && curr->nr <= r) return make_pair(curr->nm, curr->nmid);
		if (curr->nr < l || curr->nl > r) return make_pair(inf, -1);
		pair<int, int> res = min(minInRange(curr->l, l, r), minInRange(curr->r, l, r));
		if (curr->id >= l && curr->id <= r) res = min(make_pair(curr->v, curr->id), res);
		return res;
	}

	void insert(int id, int v) { rt = addNode(rt, id, v, randInt()); }
	void erase(int id) { rt = deleteNode(rt, id); }
	Node* split(int sid) { Node* l, *r; split(rt, l, r, sid); rt = l; return r; }
	void merge(Node* r, int sid) { rt = merge(rt, r, sid); }
	int minID() const { assert(rt != NULL); return rt->nmid; }
	int minInRange(int l, int r) const { return minInRange(rt, l, r).second; }
};

int n, p[200005], res[200005];
Treap odd, even;
set<int> used;

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", p + i);
		if (i % 2 == 0) odd.insert(i, p[i]);
		else even.insert(i, p[i]);
	}
	used.insert(n);
	for (int i = 0; i < n; i += 2) {
		int mid = odd.minID();
		int rb = *used.upper_bound(mid) - 1;
		assert(mid < rb);
		int mid2 = even.minInRange(mid, rb);
		assert(mid2 != -1);
		used.insert(mid);
		used.insert(mid2);
		res[i] = p[mid];
		res[i + 1] = p[mid2];
		odd.erase(mid);
		even.erase(mid2);
		Treap oddMid(odd.split(mid));
		Treap oddRight(oddMid.split(mid2));
		Treap evenMid(even.split(mid));
		Treap evenRight(evenMid.split(mid2));
		odd.merge(evenMid.rt, mid);
		odd.merge(oddRight.rt, mid2);
		even.merge(oddMid.rt, mid);
		even.merge(evenRight.rt, mid);
		vector<int> debugOdd, debugEven;
		if (i != n - 2) {
			odd.rt->show(debugOdd);
			even.rt->show(debugEven);
		}
	}
	for (int i = 0; i < n; i++) printf("%d ", res[i]);
#ifdef LOCAL_MSVC_DEBUG
	system("pause");
#endif
	return 0;
}


Compiler output:
a.cc:44:43: warning: integer overflow in expression of type 'int' results in '-2147483648' [-Woverflow]
   44 |         static const int infw = (RAND_MAX + 1) * (RAND_MAX + 1);
      |                                           ^
a.cc:44:60: warning: integer overflow in expression of type 'int' results in '-2147483648' [-Woverflow]
   44 |         static const int infw = (RAND_MAX + 1) * (RAND_MAX + 1);
      |                                                            ^
a.cc:44:48: error: overflow in constant expression [-fpermissive]
   44 |         static const int infw = (RAND_MAX + 1) * (RAND_MAX + 1);
      |                                 ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
a.cc:44:63: error: overflow in constant expression [-fpermissive]
   44 |         static const int infw = (RAND_MAX + 1) * (RAND_MAX + 1);
      |                                                               ^
a.cc: In member function 'int Treap::randInt() const':
a.cc:43:57: warning: integer overflow in expression of type 'int' results in '-2147483648' [-Woverflow]
   43 |         int randInt() const { return rand() * (RAND_MAX + 1) + rand(); }
      |                                                         ^