Language: C++

#include <cstdio>
#include <algorithm>
#include <set>
#include <utility>
static const int MAXN = 2e5 + 4;
 
int n;
int a[MAXN], p[MAXN];
int b[MAXN], top = 0;
 
struct rmq {
    static const int LOGN = 18;
    std::pair<int, int> f[LOGN][MAXN];
    inline void build(int n, int *a) {
        for (int i = 0; i < n; ++i) f[0][i] = std::make_pair(a[i], i);
        for (int j = 1; j < LOGN; ++j)
            for (int i = 0; i <= n - (1 << j); ++i)
                f[j][i] = std::min(f[j - 1][i], f[j - 1][i + (1 << (j - 1))]);
    }
    inline std::pair<int, int> query(int l, int r) {
        if (l == r) return f[0][l];
        int sz = 8 * sizeof(int) - __builtin_clz(r - l) - 1;
        return std::min(f[sz][l], f[sz][r - (1 << sz) + 1]);
    }
} all, even, odd;
 
struct cmp_peek {
    inline bool operator ()(const std::pair<int, int>& a, const std::pair<int, int>& b)
    {
        int ua = ((a.first & 1) ? odd : even).query(a.first, a.second).first;
        int ub = ((b.first & 1) ? odd : even).query(b.first, b.second).first;
        return ua < ub;
    }
};
 
std::set<std::pair<int, int>, cmp_peek> s;
 
void solve(int l, int r)
{
    auto u = ((l & 1) ? odd : even).query(l, r);
    auto v = ((r & 1) ? odd : even).query(l, r);
    int pu = u.second, pv = v.second;
    b[top++] = u.first;
    b[top++] = v.first;
    if (l <= pu - 1) s.insert(std::make_pair(l, pu - 1));
    if (pu + 1 <= pv - 1) s.insert(std::make_pair(pu + 1, pv - 1));
    if (pv + 1 <= r) s.insert(std::make_pair(pv + 1, r));
}
 
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]), p[--a[i]] = i;
 
    all.build(n, a);
    for (int i = 0; i < n; ++i) b[i] = (i & 1) ? MAXN : a[i];
    even.build(n, b);
    for (int i = 0; i < n; ++i) b[i] = (i & 1) ? a[i] : MAXN;
    odd.build(n, b);
 
    s.insert(std::make_pair(0, n - 1));
    while (!s.empty()) {
        auto r = *s.begin(); s.erase(s.begin());
        solve(r.first, r.second);
    }
 
    for (int i = 0; i < n; ++i) printf("%d%c", b[i] + 1, i == n - 1 ? '\n' : ' ');
    return 0;
}

Compiler output:
In file included from /usr/include/c++/14/set:62,
                 from a.cc:3:
/usr/include/c++/14/bits/stl_tree.h: In instantiation of 'static const _Key& std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_S_key(_Const_Link_type) [with _Key = std::pair<int, int>; _Val = std::pair<int, int>; _KeyOfValue = std::_Identity<std::pair<int, int> >; _Compare = cmp_peek; _Alloc = std::allocator<std::pair<int, int> >; _Const_Link_type = const std::_Rb_tree_node<std::pair<int, int> >*]':
/usr/include/c++/14/bits/stl_tree.h:2116:47:   required from 'std::pair<std::_Rb_tree_node_base*, std::_Rb_tree_node_base*> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_get_insert_unique_pos(const key_type&) [with _Key = std::pair<int, int>; _Val = std::pair<int, int>; _KeyOfValue = std::_Identity<std::pair<int, int> >; _Compare = cmp_peek; _Alloc = std::allocator<std::pair<int, int> >; key_type = std::pair<int, int>]'
 2116 |           __comp = _M_impl._M_key_compare(__k, _S_key(__x));
      |                                                ~~~~~~^~~~~
/usr/include/c++/14/bits/stl_tree.h:2169:4:   required from 'std::pair<std::_Rb_tree_iterator<_Val>, bool> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_unique(_Arg&&) [with _Arg = std::pair<int, int>; _Key = std::pair<int, int>; _Val = std::pair<int, int>; _KeyOfValue = std::_Identity<std::pair<int, int> >; _Compare = cmp_peek; _Alloc = std::allocator<std::pair<int, int> >]'
 2169 |         = _M_get_insert_unique_pos(_KeyOfValue()(__v));
      |           ^~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_set.h:523:25:   required from 'std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(value_type&&) [with _Key = std::pair<int, int>; _Compare = cmp_peek; _Alloc = std::allocator<std::pair<int, int> >; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, cmp_peek, std::allocator<std::pair<int, int> > >::const_iterator; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other = std::allocator<std::pair<int, int> >; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key> = __gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::rebind<std::pair<int, int> >; typename _Alloc::value_type = std::pair<int, int>; value_type = std::pair<int, int>]'
  523 |           _M_t._M_insert_unique(std::move(__x));
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
a.cc:45:30:   required from here
   45 |     if (l <= pu - 1) s.insert(std::make_pair(l, pu - 1));
      |                      ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_tree.h:768:15: error: static assertion failed: comparison object must be invocable as const
  768 |               is_invocable_v<const _Compare&, const _Key&, const _Key&>,
      |               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_tree.h:768:15: note: 'std::is_invocable_v<const cmp_peek&, const std::pair<int, int>&, const std::pair<int, int>&>' evaluates to false