CF1906E

// Problem: E. Merge Not Sort
// Contest: Codeforces - 2023-2024 ICPC, Asia Jakarta Regional Contest (Online Mirror, Unrated, ICPC Rules, Teams
// Preferred) URL: https://codeforces.com/problemset/problem/1906/E Memory Limit: 1024 MB Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#ifndef __DEBUG__
#define dbg(...) 42
#endif
template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

namespace rngs = std::ranges;
using ll = long long;
using a2l = array<ll, 2>;
using vl = vector<ll>;

void solve()
{
    ll n;
    cin >> n;
    vl ps(2 * n);
    for (auto &x : ps)
        cin >> x;

    ps.push_back(2 * n + 1);
    vector<a2l> opt;
    for (ll i = 0, j = 0; i < 2 * n;) {
        j = i;
        while (j + 1 < 2 * n + 1 && ps[j] > ps[j + 1])
            ++j;
        // dbg(i, j, ps[j], ps[j + 1]);
        opt.push_back({j - i + 1, i});
        i = j + 1;
    }

    dbg(opt);
    vl sol;
    auto dfs = [&](auto &&self, ll id, ll acc) -> bool {
        if (acc == n)
            return true;
        if (acc > n)
            return false;
        if (id >= opt.size())
            return false;
        sol.push_back(id);
        if (self(self, id + 1, acc + opt[id][0]))
            return true;
        sol.pop_back();
        return self(self, id + 1, acc);
    };
    auto ans = dfs(dfs, 0, 0);
    dbg(sol, ans);
    if (!ans) {
        cout << -1 << '\n';
        return;
    }

    vl v1, v2;
    for (ll i = 0, j = 0; i < 2 * n; ++i) {
        if (j < sol.size() && opt[sol[j]][0] + opt[sol[j]][1] <= i)
            ++j;

        if (j < sol.size() && i >= opt[sol[j]][1] && i < opt[sol[j]][1] + opt[sol[j]][0])
            v1.push_back(ps[i]);
        else
            v2.push_back(ps[i]);
    }
    assert(v1.size() == n);
    assert(v2.size() == n);
    for (auto x : v1)
        cout << x << ' ';
    cout << '\n';
    for (auto x : v2)
        cout << x << ' ';
    cout << '\n';
}

int main(int argc, char **argv)
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    ll t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
};