1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
#include <bits/stdc++.h>
namespace Task {
const int MAXN = 200000;
int M;
inline void init(const int n) {
for (M = 1; M < n + 2; M <<= 1)
;
}
struct SegmentTree {
int d[MAXN * 4];
inline void maintain(int k) { d[k] = std::min(d[k << 1], d[k << 1 | 1]); }
inline void build() {
for (register int i = M - 1; i; i--) maintain(i);
}
inline int query(int s, int t) const {
register int ret = INT_MAX;
for (s = s + M - 1, t = t + M + 1; s ^ t ^ 1; s >>= 1, t >>= 1) {
(~s & 1) ? ret = std::min(ret, d[s ^ 1]) : 0;
(t & 1) ? ret = std::min(ret, d[t ^ 1]) : 0;
}
return ret;
}
};
SegmentTree even, odd;
int a[MAXN + 1], pos[MAXN + 1];
struct Node {
int l, r, x;
Node(int l, int r, int x) : l(l), r(r), x(x) {}
inline bool operator<(const Node &b) const { return x > b.x; }
};
template <typename T>
class PriorityQueue : public std::priority_queue<T> {
private:
#define super std::priority_queue<T>
public:
inline void reserve(const int n) { super::c.reserve(n); }
#undef super
};
inline void initRmq(const int n, const int *a) {
init(n);
for (register int i = 1; i <= n; i++) {
if (i & 1) {
odd.d[M + i] = a[i], even.d[M + i] = INT_MAX;
} else {
even.d[M + i] = a[i], odd.d[M + i] = INT_MAX;
}
}
even.build(), odd.build();
}
inline void solve() {
std::ios::sync_with_stdio(false), std::cin.tie(NULL), std::cout.tie(NULL);
register int n;
std::cin >> n;
for (register int i = 1; i <= n; i++) std::cin >> a[i], pos[a[i]] = i;
initRmq(n, a);
static PriorityQueue<Node> q;
q.reserve(n * 2);
q.push(Node(1, n, odd.query(1, n)));
const SegmentTree *t[2] = {&even, &odd};
while (!q.empty()) {
Node d = q.top();
q.pop();
register int l = d.l, r = d.r;
register int p1 = pos[d.x], p2 = pos[t[~p1 & 1]->query(p1 + 1, r)];
std::cout << a[p1] << ' ' << a[p2] << ' ';
if (l < p1) q.push(Node(l, p1 - 1, t[l & 1]->query(l, p1 - 1)));
if (p1 < p2 - 1)
q.push(Node(p1 + 1, p2 - 1, t[~p1 & 1]->query(p1 + 1, p2 - 1)));
if (p2 < r) q.push(Node(p2 + 1, r, t[~p2 & 1]->query(p2 + 1, r)));
}
}
}
int main() {
Task::solve();
return 0;
}
|
