#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; }