Language: C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <set>
#include <cmath>
using namespace std;

// Range Minimum Query
class SegmentTree {
    int n;
    vector<int> dat;

    // i は接点の番号、l, rはその接点が[l, r)に対応していることを示す
    int query_sub(int a, int b, int i, int l, int r) {
        if (r <= a || b <= l) return INT_MAX;
        if (a <= l && r <= b)
            return dat[i];
        else {
            int vl = query_sub(a, b, i * 2 + 1, l, (l + r) / 2);
            int vr = query_sub(a, b, i * 2 + 2, (l + r) / 2, r);
            return min(vl, vr);
        }
    }

public:
    // 葉がn個のセグメント木
    // 実際の葉の数は完全二分木にしているので少し増える
    SegmentTree(int n_) {
        n = 1;
        while (n < n_) n *= 2;
        dat = vector<int>(2 * n - 1, INT_MAX);
    }
    // i に x を入れる
    void update(int i, int x) {
        i += n - 1;
        dat[i] = x;
        while (i > 0) {
            i = (i - 1) / 2;
            dat[i] = min(dat[i * 2 + 1], dat[i * 2 + 2]);
        }
    }
    // [a, b) の最小値を求める
    int query(int a, int b) { return query_sub(a, b, 0, 0, n); }
    // 配列にアクセス
    int at(int i) { return dat[i + n - 1]; }
};

int main(){
    int N;
    cin >> N;
    vector<int> p(N), pinv(N);
    for(int i=0; i<N; i++){
        cin >> p[i];
        p[i]--;
        pinv[p[i]] = i;
    }

    SegmentTree st[2] = {SegmentTree(N), SegmentTree(N)};

    for(int i=0; i<N; i+=2)
        st[0].update(i, p[i]);
    for(int i=1; i<N; i+=2)
        st[1].update(i, p[i]);

    vector<int> ans;
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
    pq.push(make_tuple(st[0].query(0, N), 0, N-1));
    while(!pq.empty()){
        int mn_ev, mn_od, l, r;
        tie(mn_ev, l, r) = pq.top();
        pq.pop();

        int id_ev, id_od;
        id_ev = pinv[mn_ev];
        mn_od = st[(id_ev+1)%2].query(id_ev+1, r+1);
        id_od = pinv[mn_od];
        ans.push_back(mn_ev);
        ans.push_back(mn_od);

        if(l != id_ev){
            int mn = st[l%2].query(l, id_ev);
            pq.push(make_tuple(mn, l, id_ev-1));
        }
        if(r != id_od){
            int mn = st[(id_od+1)%2].query(id_od+1, r+1);
            pq.push(make_tuple(mn, id_od+1, r));
        }
        if(id_od != id_ev+1){
            int mn = st[(id_ev+1)%2].query(id_ev+1, id_od);
            pq.push(make_tuple(mn, id_ev+1, id_od-1));
        }
    }
    for(auto x : ans)
        cout << x+1 << " ";
    cout << endl;
    return 0;
}


Compiler output:
a.cc: In member function 'int SegmentTree::query_sub(int, int, int, int, int)':
a.cc:18:38: error: 'INT_MAX' was not declared in this scope
   18 |         if (r <= a || b <= l) return INT_MAX;
      |                                      ^~~~~~~
a.cc:9:1: note: 'INT_MAX' is defined in header '<climits>'; this is probably fixable by adding '#include <climits>'
    8 | #include <cmath>
  +++ |+#include <climits>
    9 | using namespace std;
a.cc: In constructor 'SegmentTree::SegmentTree(int)':
a.cc:34:38: error: 'INT_MAX' was not declared in this scope
   34 |         dat = vector<int>(2 * n - 1, INT_MAX);
      |                                      ^~~~~~~
a.cc:34:38: note: 'INT_MAX' is defined in header '<climits>'; this is probably fixable by adding '#include <climits>'