Language: C++

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#include<set>
#include<complex>
#include<string>
#include<cstring>
using namespace std;
#define rep2(x,from,to) for(int x=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
#define INF 100000000
#define debug(x) cout<<#x<<": "<<x<<endl

#define all(x) x.begin(),x.end()
typedef pair<int,int> P;
typedef pair<int,P> PP;
int ba[200005];
int N;
int p[200005];
//
const int MAX_N=200006;
int n,dat[4*MAX_N];
int b_dat[4*MAX_N];
void init(int n_)
{
	n=1;
	while(n<n_)n*=2;
	rep(i,2*n-1)
	{
		b_dat[i]=INT_MAX;
		dat[i]=INT_MAX;
	}
}
void update(int k,int a)
{
	int kk=k+n-1;
	dat[kk]=a;
	while(kk)
	{
		kk=(kk-1)/2;
		dat[kk]=min(dat[kk*2+1],dat[kk*2+2]);
	}
}
void b_update(int k,int a)
{
	int kk=k+n-1;
	b_dat[kk]=a;
	while(kk)
	{
		kk=(kk-1)/2;
		b_dat[kk]=min(b_dat[kk*2+1],b_dat[kk*2+2]);
	}
}
int query(int a,int b,int k,int l,int r)
{
	if(r<=a||b<=l)return INT_MAX;
	if(a<=l&&r<=b)return dat[k];
	else
	{
		int vl=query(a,b,k*2+1,l,(l+r)/2);
		int vr=query(a,b,k*2+2,(l+r)/2,r);
		return min(vl,vr);
	}
}
int b_query(int a,int b,int k,int l,int r)
{
	if(r<=a||b<=l)return INT_MAX;
	if(a<=l&&r<=b)return b_dat[k];
	else
	{
		int vl=b_query(a,b,k*2+1,l,(l+r)/2);
		int vr=b_query(a,b,k*2+2,(l+r)/2,r);
		return min(vl,vr);
	}
}
//
vector<P> ans;
vector<P> saiki(int saiki_f,int saiki_e)
{
	vector<P> res;
	if(saiki_f>=saiki_e)
	{
		return res;
	}
	if(saiki_f+2==saiki_e)
	{
		res.push_back(P(p[saiki_f],p[saiki_f+1]));
		return res;
	}
	int sub_first,sub_second;
	if(saiki_f%2==0)
	{
		sub_first=query(saiki_f,saiki_e,0,0,n);
		sub_second=b_query(ba[sub_first],saiki_e,0,0,n);
	}
	else
	{
		sub_first=b_query(saiki_f,saiki_e,0,0,n);
		sub_second=query(ba[sub_first],saiki_e,0,0,n);
	}
	int k;
	int one_ind=0;
	int two_ind=0;
	int three_ind=0;
	vector<P> one=saiki(saiki_f,ba[sub_first]);
	vector<P> two=saiki(ba[sub_first]+1,ba[sub_second]);
	vector<P> three=saiki(ba[sub_second]+1,saiki_e);
	res.push_back(P(sub_first,sub_second));
	while(!(one_ind==one.size()&&two_ind==two.size()&&three_ind==three.size()))
	{
		k=INF;
		if(one_ind!=one.size())
		{
			if(one[one_ind].first<k)k=one[one_ind].first;
		}
		if(two_ind!=two.size())
		{
			if(two[two_ind].first<k)k=two[two_ind].first;
		}
		if(three_ind!=three.size())
		{
			if(three[three_ind].first<k)k=three[three_ind].first;
		}
		if(k==one[one_ind].first)
		{
			res.push_back(one[one_ind]);
			one_ind++;
		}
		if(k==two[two_ind].first)
		{
			res.push_back(two[two_ind]);
			two_ind++;
		}
		if(k==three[three_ind].first)
		{
			res.push_back(three[three_ind]);
			three_ind++;
		}
	}
	return res;
}
int main()
{
	cin>>N;
	init(N);
	rep(i,N)
	{
		cin>>p[i];
		ba[p[i]]=i;
		if(i%2==0)
		{
			update(i,p[i]);
		}
		else b_update(i,p[i]);
	}
	ans=saiki(0,N);
	rep(i,ans.size())
	{
		cout<<ans[i].first<<" "<<ans[i].second;
		if(i==ans.size()-1)cout<<endl;
		else cout<<" ";
	}
	return 0;
}

Compiler output:
a.cc: In function 'void init(int)':
a.cc:34:26: error: 'INT_MAX' was not declared in this scope
   34 |                 b_dat[i]=INT_MAX;
      |                          ^~~~~~~
a.cc:12:1: note: 'INT_MAX' is defined in header '<climits>'; this is probably fixable by adding '#include <climits>'
   11 | #include<cstring>
  +++ |+#include <climits>
   12 | using namespace std;
a.cc: In function 'int query(int, int, int, int, int)':
a.cc:60:30: error: 'INT_MAX' was not declared in this scope
   60 |         if(r<=a||b<=l)return INT_MAX;
      |                              ^~~~~~~
a.cc:60:30: note: 'INT_MAX' is defined in header '<climits>'; this is probably fixable by adding '#include <climits>'
a.cc: In function 'int b_query(int, int, int, int, int)':
a.cc:71:30: error: 'INT_MAX' was not declared in this scope
   71 |         if(r<=a||b<=l)return INT_MAX;
      |                              ^~~~~~~
a.cc:71:30: note: 'INT_MAX' is defined in header '<climits>'; this is probably fixable by adding '#include <climits>'