#include "hieroglyphs.h"
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
struct SegTree
{
ll n;
vector<pair<ll, ll>> st;
SegTree(ll sz = 0)
{
n = sz;
st.resize(n << 1, make_pair(0, -1));
}
void build()
{
for (ll i = n - 1; i >= 1; i--)
st[i] = max(st[i << 1], st[i << 1 | 1]);
}
void modify(ll p, pair<ll, ll> val)
{
for (st[p + n] = max(st[p + n], val), p += n; p > 1; p >>= 1)
st[p >> 1] = max(st[p], st[p ^ 1]);
}
pair<ll, ll> query(ll l, ll r)
{
pair<ll, ll> ans = make_pair(0, -1);
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1)
{
if (l & 1)
ans = max(ans, st[l++]);
if (r & 1)
ans = max(ans, st[--r]);
}
return ans;
}
};
std::vector<int> ucs(std::vector<int> a, std::vector<int> b)
{
{
set<ll> sa, sb;
for (ll i : a)
sa.insert(i);
for (ll i : b)
sb.insert(i);
vector<int> nv;
for (ll i : a)
if (sb.count(i))
nv.push_back(i);
a = nv;
nv.clear();
for (ll i : b)
if (sa.count(i))
nv.push_back(i);
b = nv;
}
vector<int> ans;
set<ll> s;
map<ll, vector<ll>> freqb;
map<ll, ll> cnt;
for (ll i : a)
cnt[i]++;
for (ll i = 0; i < b.size(); i++)
freqb[b[i]].push_back(i);
vector<ll> event[a.size() + 1];
for (ll i = 0; i < a.size(); i++)
if (cnt[a[i]] == 2)
{
if (s.count(a[i]))
event[i].push_back(freqb[a[i]].back());
else
event[i + 1].push_back(freqb[a[i]].back()), s.insert(a[i]);
}
s.clear();
for (ll i = 0; i < a.size(); i++)
{
for (ll j : event[i])
if (s.count(j))
s.erase(j);
else
s.insert(j);
auto [l, r] = array<ll, 2>{freqb[a[i]].front(), freqb[a[i]].back()};
auto it = s.upper_bound(l);
if (it != s.end() and *it < r)
return {-1};
}
vector<pair<ll, ll>> v;
for (ll i = 0; i < a.size(); i++)
for (ll j : freqb[a[i]])
v.push_back(make_pair(i, j));
SegTree st(v.size());
pair<ll, ll> dp[v.size()];
ll ptr = 0;
for (ll i = 0; i < v.size(); i++)
{
auto [a, b] = v[i];
while (ptr < i and v[ptr].first < a)
st.modify(v[ptr].second, make_pair(dp[ptr].first, ptr)), ptr++;
dp[i] = st.query(0, b - 1);
dp[i].first++;
}
if (v.empty()) return {};
ll best = max_element(dp, dp + v.size()) - dp;
while (best + 1)
ans.push_back(b[v[best].second]), best = dp[best].second;
reverse(ans.begin(), ans.end());
if (ans.size() != cnt.size()) return {-1};
return ans;
}
