Language: C++


#define _CRT_SECURE_NO_WARNINGS

#define N (1<<17)
#define MODULO (1000000007)
#define HA1 (2420609)
#define HA2 (19260817)

#include <cstdio>
#include <iostream>
#include <fstream>
#include <sstream>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <complex>
using namespace std;

namespace MRAND
{
	class MRNDS
	{
	public:
		int ngf;
		unsigned int lgf;
		MRNDS()
		{
			ngf = HA1*HA2;
			lgf = HA1 - HA2*ngf;
		}
		MRNDS(long long rgf)
		{
			lgf = rgf&((1LL << 32) - 1LL);
			ngf = (rgf >> 31);
			ngf += 2LL * lgf;
			ngf *= HA2;
			lgf += HA1;
		}
		MRNDS operator* (const MRNDS &mrs)const
		{
			MRNDS Res;
			Res.ngf += ngf*mrs.lgf;
			Res.ngf -= mrs.ngf*lgf;
			Res.ngf *= HA1;
			Res.lgf *= HA2;
			return Res;
		}
	}curl, curr;
	inline void InitRand(MRNDS &Lmrs, MRNDS &Rmrs)
	{
		curl = Lmrs;
		curr = Rmrs;
		curl = curl*curr;
		curl.ngf += HA2;
	}
	inline int GetRand()
	{
		curl = curl*curr;
		return (curl.lgf*HA1 - curr.ngf*HA2);
	}
}

class INTERVAL
{
public:
	int mn, L, R;
	INTERVAL() {};
	bool operator< (const INTERVAL &seg)const
	{
		return mn > seg.mn;
	}
};

int n, cnt, nn;
int a[2][N], pos[N];
int Ans[N];
int tr[2][N << 1];
priority_queue<INTERVAL> PQ;

inline void SMTBuild()
{
	for (nn = 1;nn < n;nn <<= 1);
	for (int od = 0;od <= 1;od++)
	{
		for (int i = nn - 1;i < (nn << 1) - 1;i++)
		{
			tr[od][i] = a[od][i - nn + 1];
		}
		for (int i = nn - 2;i >= 0;i--)
		{
			tr[od][i] = min(tr[od][(i << 1) + 1], tr[od][(i << 1) + 2]);
		}
	}
}

inline int SMTQuery(int od, int L, int R, int X = 0, int Y = nn - 1, int pp = 0)
{
	if (Y<L || X>R)
	{
		return INT_MAX;
	}
	if (X >= L&&Y <= R)
	{
		return tr[od][pp];
	}
	return min(SMTQuery(od, L, R, X, X + ((Y - X) >> 1), (pp << 1) + 1),
		SMTQuery(od, L, R, X + 1 + ((Y - X) >> 1), Y, (pp << 1) + 2));
}

int main()
{
	scanf("%d", &n);
	for (int i = 0;i < n;i++)
	{
		int tmp;
		scanf("%d", &tmp);
		pos[tmp] = i;
		a[i & 1][i] = tmp;
		a[!(i & 1)][i] = INT_MAX;
	}
	SMTBuild();
	INTERVAL beg;
	beg.L = 0, beg.R = n - 1, beg.mn = SMTQuery(0, 0, n - 1);
	PQ.push(beg);
	while (!PQ.empty())
	{
		//throw;
		INTERVAL curi = PQ.top();
		PQ.pop();
		Ans[cnt++] = curi.mn;
		Ans[cnt++] = SMTQuery(!(pos[curi.mn] & 1), pos[curi.mn] + 1, curi.R);
		if (curi.L != pos[curi.mn])
		{
			INTERVAL tmp;
			tmp.L = curi.L, tmp.R = pos[curi.mn] - 1;
			tmp.mn = SMTQuery(curi.L & 1, curi.L, pos[curi.mn] - 1);
			PQ.push(tmp);
		}
		int vr = pos[Ans[cnt - 1]];
		if (pos[curi.mn] + 1 != vr)
		{
			INTERVAL tmp;
			tmp.L = pos[curi.mn] + 1, tmp.R = vr - 1;
			tmp.mn = SMTQuery(!(pos[curi.mn] & 1), pos[curi.mn] + 1, vr - 1);
			PQ.push(tmp);
		}
		if (vr != curi.R)
		{
			INTERVAL tmp;
			tmp.L = vr + 1, tmp.R = curi.R;
			tmp.mn = SMTQuery(!(vr & 1), vr + 1, curi.R);
			PQ.push(tmp);
		}
	}
	for (int i = 0;i < cnt - 1;i++)
	{
		printf("%d ", Ans[i]);
	}
	printf("%d\n", Ans[cnt - 1]);
	//system("pause");
	return 0;
}


Compiler output:
a.cc: In constructor 'MRAND::MRNDS::MRNDS()':
a.cc:36:34: warning: integer overflow in expression of type 'int' results in '1036979473' [-Woverflow]
   36 |                         ngf = HA1*HA2;
      |                                  ^
a.cc: In function 'int SMTQuery(int, int, int, int, int, int)':
a.cc:108:24: error: 'INT_MAX' was not declared in this scope
  108 |                 return INT_MAX;
      |                        ^~~~~~~
a.cc:25:1: note: 'INT_MAX' is defined in header '<climits>'; this is probably fixable by adding '#include <climits>'
   24 | #include <complex>
  +++ |+#include <climits>
   25 | using namespace std;
a.cc: In function 'int main()':
a.cc:127:34: error: 'INT_MAX' was not declared in this scope
  127 |                 a[!(i & 1)][i] = INT_MAX;
      |                                  ^~~~~~~
a.cc:127:34: note: 'INT_MAX' is defined in header '<climits>'; this is probably fixable by adding '#include <climits>'