#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int medians[N], tab[2 * N + 10], used[2 * N + 10], sign[2 * N + 10], mini[N], maxi[N];
priority_queue <pair<int, int>> wieksze, mniejsze;
void set_tab(int i, int a) {
if(sign[2 * i - a] == -1) tab[2 * i - a] = mini[i];
if(sign[2 * i - a] == 0) tab[2 * i - a] = medians[i];
if(sign[2 * i - a] == 1) tab[2 * i - a] = maxi[i];
}
int main() {
//-1 mniejsza, 0 rowna, +1 wieksza
int n; cin >> n;
for(int i = 1; i <= n; i++) {
cin >> medians[i];
}
for(int i = n; i >= 1; i--) {
mini[i] = min(mini[i + 1], medians[i]);
maxi[i] = max(maxi[i + 1], medians[i]);
}
tab[1] = medians[1];
used[tab[1]] = true;
for(int i = 2; i <= n; i++) {
if(medians[i] == medians[i - 1]) {
sign[2 * i - 1] = -1;
sign[2 * i - 2] = 1;
}
if(medians[i - 1] < medians[i]) {
if(used[medians[i]]) {
sign[2 * i - 1] = 1;
sign[2 * i - 2] = 1;
}
else {
sign[2 * i - 1] = 0;
sign[2 * i - 2] = 1;
}
}
if(medians[i - 1] > medians[i]) {
if(used[medians[i]]) {
sign[2 * i - 1] = -1;
sign[2 * i - 2] = -1;
}
else {
sign[2 * i - 1] = 0;
sign[2 * i - 2] = -1;
}
}
set_tab(i, 1);
set_tab(i, 2);
used[medians[i]] = true;
}
// for(int i = 1; i <= 2 * n - 1; i++) {
// cout << sign[i] << ' ' << tab[i] << ", ";
// }
// cout << '\n';
for(int i = 2 * n - 1; i >= 1; i--) {
if(sign[i] == -1) mniejsze.push({tab[i], i});
if(sign[i] == 1) wieksze.push({tab[i], i});
}
for(int i = 2 * n - 1; i >= 1; i--) {
if(used[i]) continue;
if(!wieksze.empty()) {
tab[wieksze.top().second] = i;
wieksze.pop();
}
else if(!mniejsze.empty()) {
tab[mniejsze.top().second] = i;
mniejsze.pop();
}
else break;
}
for(int i = 1; i <= 2 * n - 1; i++) {
cout << tab[i] << ' ';
}
return 0;
}
