Language: C++

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
#define sc(a) scanf("%d", &a)
#define sc2(a,b) scanf("%d%d", &a, &b)
#define sc3(a,b,c) scanf("%d%d%d", &a, &b, &c)
#define pri(x) printf("%d\n", x)
#define mp make_pair
#define pb push_back
#define BUFF ios::sync_with_stdio(false);
#define imprime(v) for(int X=0;X<v.size();X++) printf("%d ", v[X]); printf("\n");
#define endl "\n"
const int INF= 0x3f3f3f3f;
const long double pi= acos(-1);
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector< vector< int > > vvi;
const int MOD=1e9+7;
const ll LINF=0x3f3f3f3f3f3f3f3f;

const int MAXN = 200005;

int p[MAXN];

int m(int b, int e) { return (b + e) / 2;}
class RMQ {
  vector<int> tr;
  public:

  void init(int N) {
    tr.resize(4 * N + 100, -1);
  }

  void update(int nd, int b, int e, int i) {
    if(i > e or i < b or b > e) return;
    if(b == e) {
      tr[nd] = i;
      return;
    }
    update(nd * 2, b, m(b, e), i);
    update(nd * 2 + 1, m(b, e) + 1, e, i);
    if(tr[nd * 2] == -1) tr[nd] = tr[nd * 2 + 1];
    else if(tr[nd * 2 + 1] == -1) tr[nd] = tr[nd * 2];
    else if(p[tr[nd * 2]] < p[tr[nd * 2 + 1]]) tr[nd] = tr[nd * 2];
    else tr[nd] = tr[nd * 2 + 1];
  }

  int query(int nd, int b, int e, int i, int j) {
    if(i > j) return -1;
    if(i == j) return i;
    if(b > j or e < i or b > e) return -1;
    if(b >= i and e <= j) return tr[nd];
    int q1 = query(nd * 2, b, m(b, e), i, j);
    int q2 = query(nd * 2 + 1, m(b, e) + 1, e, i, j);
    if(q1 == -1) return q2;
    if(q2 == -1) return q1;
    if(p[q1] < p[q2]) return q1;
    return q2;
  }
};
RMQ even;
int n;
RMQ odd;
vector<ii> ans;

void go(int l, int r, vector<ii> &ret) {
  if(l >= r or r >= n or l < 0) return;
  int menorev, menorodd;
  assert((r - l) % 2 == 1);
  if((l % 2) == 0) {
    menorev = even.query(1, 0, n - 1, l, r);
    menorodd = odd.query(1, 0, n - 1, menorev + 1, r);
  }
  else {
    menorev = odd.query(1, 0, n - 1, l, r);
    menorodd = even.query(1, 0, n - 1, menorev + 1, r);
  }
  assert(menorev != -1 and menorodd != -1 and menorodd > menorev);
  vector<ii> a;
  go(l, menorev - 1, a);
  vector<ii> b;
  go(menorev + 1, menorodd - 1, b);
  vector<ii> c;
  go(menorodd + 1, r, c);
  int pta = 0;
  int ptb = 0;
  int ptc = 0;
  ret.pb(mp(p[menorev], p[menorodd]));
  while(pta < a.size() or ptb < b.size() or ptc < c.size()) {
    if(pta == a.size()) {
      if(ptb == b.size()) {
        ret.pb(c[ptc]);
        ptc++;
      }
      else if(ptc == c.size()) {
        ret.pb(b[ptb]);
        ptb++;
      }
      else if(b[ptb] < c[ptc]) {
        ret.pb(b[ptb]);
        ptb++;
      }
      else {
        ret.pb(c[ptc]);
        ptc++;
      }
    }
    else if(ptb == b.size()) {
      if(ptc == c.size()) {
        ret.pb(a[pta]);
        pta++;
      }
      else if(a[pta] < c[ptc]) {
        ret.pb(a[pta]);
        pta++;
      }
      else {
        ret.pb(c[ptc]);
        ptc++;
      }
    }
    else if(ptc == c.size()) {
      if(a[pta] < b[ptb]) {
        ret.pb(a[pta]);
        pta++;
      }
      else {
        ret.pb(b[ptb]);
        ptb++;
      }
    }
    else {
      if(a[pta] < b[ptb] and a[pta] < c[ptc]) {
        ret.pb(a[pta]);
        pta++;
      }
      else if(b[ptb] < a[pta] and b[ptb] < c[ptc]) {
        ret.pb(b[ptb]);
        ptb++;
      }
      else {
        ret.pb(c[ptc]);
        ptc++;
      }
    } 
  }
}

int main() {
  sc(n);
  even.init(n * 3);
  odd.init(n * 3);
  for(int i = 0; i < n; i++) {
    sc(p[i]);
  }
  for(int i = 0; i < n; i++) {
    if((i % 2) == 0) {
      even.update(1, 0, n - 1, i);
    }
    else odd.update(1, 0, n - 1, i);
  }
  go(0, n - 1, ans);
  for(int i = 0; i < ans.size(); i++) {
    if(i != 0) printf(" ");
    printf("%d %d", ans[i].first, ans[i].second);
  }
  printf("\n");
  return 0;
}




Compiler output:
a.cc: In function 'void go(int, int, std::vector<std::pair<int, int> >&)':
a.cc:84:3: error: 'assert' was not declared in this scope
   84 |   assert((r - l) % 2 == 1);
      |   ^~~~~~
a.cc:15:1: note: 'assert' is defined in header '<cassert>'; this is probably fixable by adding '#include <cassert>'
   14 | #include <utility>
  +++ |+#include <cassert>
   15 | #include <vector>