Language: C++

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
using P = pair<int, int>;
const ll MOD = 1000000007;

const int INF = 100000000;

class IndexSegmentTree{
private:
    int n;
    vector<int> dat;
    vector<int> v;
public:
    void init(int n_){
        n = 1;
        while(n < n_) n *= 2;
        dat.assign(2*n-1, -1);
        v.assign(n, INF);
    }
    // k: index(0-indexed), a: value
    void update(int p, int a){
        v[p] = a;
        int k = p + n - 1;
        dat[k] = p;
        while(k>0){
            k = (k-1)/2;
            if(dat[k*2+2]==-1 || v[dat[k*2+1]] <= v[dat[k*2+2]]){
                dat[k] = dat[k*2+1];
            }else{
                dat[k] = dat[k*2+2];
            }
        }
    }
    // query(a, b) =>  minimum in [a,b]
    int query(int a, int b){
        return _query(a, b, 0, 0, n-1);
    }
    // v[dat[k]] is minimum in [l,r]
    int _query(int a, int b, int k, int l, int r){
        if(r<a||b<l) return -1;
        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+1, r);
            if(vr == -1){
                return vl;
            }else if(vl == -1){
                return vr;
            }else{
                if (v[vl] > v[vr]){
                    return vr;
                }else{
                    return vl;
                }
            }
        }
    }
    // k: index(0-indexed)
    int get(int k){
        return v[k];
    }
};

IndexSegmentTree seg[2];
vector<int> p;
vector<P> pairs;
vector<vector<int>> G;

int dfs(int l, int r, int m){
    // [l, r]
    int min_idx = seg[m].query(l, r);
    assert(min_idx != -1);
    int next_m = m ^ 1;
    int pair_idx = seg[next_m].query(min_idx + 1, r);
    assert(pair_idx != -1);

    int i = pairs.size();
    assert(i == G.size());
    pairs.emplace_back(p[min_idx], p[pair_idx]);
    G.push_back({});

    if(l < min_idx){
        G[i].push_back(dfs(l, min_idx - 1, m));
    }
    if(pair_idx - min_idx > 2){
        G[i].push_back(dfs(min_idx + 1, pair_idx - 1, next_m));
    }
    if(pair_idx < r){
        G[i].push_back(dfs(pair_idx, r, m));
    }

    return i;
}

int main(){
    int N;
    cin >> N;

    seg[0].init(N);
    seg[1].init(N);

    p.resize(N);
    for(int i=0;i<N;i++){
        cin >> p[i];
        seg[i % 2].update(i, p[i]);
    }

    int root = dfs(0, N-1, 0);
    assert(root == 0);

    priority_queue<P, vector<P>, greater<P>> que;
    que.emplace(pairs[root].first, root);

    bool start = true;
    while(que.size()){
        P p = que.top(); que.pop();
        int v = p.second;
        if(!start){
            cout << " ";
        }
        start = false;
        cout << pairs[v].first << " " << pairs[v].second;
        for(int to : G[v]){
            que.emplace(pairs[to].first, to);
        }
    }
    cout << endl;

    return 0;
}

Compiler output:
a.cc: In function 'int dfs(int, int, int)':
a.cc:75:5: error: 'assert' was not declared in this scope
   75 |     assert(min_idx != -1);
      |     ^~~~~~
a.cc:3:1: note: 'assert' is defined in header '<cassert>'; this is probably fixable by adding '#include <cassert>'
    2 | #include <vector>
  +++ |+#include <cassert>
    3 | using namespace std;
a.cc: In function 'int main()':
a.cc:112:5: error: 'assert' was not declared in this scope
  112 |     assert(root == 0);
      |     ^~~~~~
a.cc:112:5: note: 'assert' is defined in header '<cassert>'; this is probably fixable by adding '#include <cassert>'
a.cc:114:5: error: 'priority_queue' was not declared in this scope
  114 |     priority_queue<P, vector<P>, greater<P>> que;
      |     ^~~~~~~~~~~~~~
a.cc:3:1: note: 'std::priority_queue' is defined in header '<queue>'; this is probably fixable by adding '#include <queue>'
    2 | #include <vector>
  +++ |+#include <queue>
    3 | using namespace std;
a.cc:114:21: error: expected primary-expression before ',' token
  114 |     priority_queue<P, vector<P>, greater<P>> que;
      |                     ^
a.cc:114:32: error: expected primary-expression before ',' token
  114 |     priority_queue<P, vector<P>, greater<P>> que;
      |                                ^
a.cc:114:43: error: expected primary-expression before '>' token
  114 |     priority_queue<P, vector<P>, greater<P>> que;
      |                                           ^~
a.cc:114:46: error: 'que' was not declared in this scope
  114 |     priority_queue<P, vector<P>, greater<P>> que;
      |                                              ^~~