给出这种限制，我们只能 4 个 4 个考虑。令 \(f_i\) 为考虑到 \(a_i\)，最长的 \(b\) 序列长 \(4f_i\)。
令 \(mx_i\) 为以 \(a_i\) 结尾的最短连续子序列包含 \(x\ y\ x\ y\) 的（不一定连续的）结构的左端点。
于是有 \(f_i=\max_{j=1}^{mx_i-1} f_j+4\)。
用前缀和优化：
\(g_i=\max_{j=1}^if_j\)。
\(f_i=g_{mx_i-1}+4\)。
dp 的时间复杂度变为 \(O(n)\)。
考虑如何求出 \(mx_i\)。
注意到如果把 \(x\) 和 \(y\) 都列出来，形如 \(\color{white}\cdots {x}\color{blue}{y}\color{green}{y}\color{white}{x}\color{red}{y}\color{white}y\cdots\)，那么这一组 \(xyxy\) 的左端点固定，右端点最左也会在 \(\color{red} y\) 上，而如果存在 \(\color{white}{x}\color{blue}{y}\color{white}{x}\color{red}{y}\) ，则一定存在 \(\color{white}{x}\color{green}{y}\color{white}{x}\color{red}{y}\)。
也就是 \(r_i\) 的最优结构中一定存在这样的一种结构：两个 \(y\) 之间一定没有其他 \(y\)。
这时问题变为对于相邻两个同颜色的位置 \(l,r\) 求最大的 \(i\in [1,l)\) 使得 \(\exists j\in(l,r) \text{ s.t. }a_i=a_j\)。
这是可持久化线段树的板子题：
令 \(nxt_i\) 为最小的满足 \(a_i=a_j,j>i\) 的 \(j\)。不存在即为 \(n+1\)。
然后按照 \(nxt_i\) 排序，在 \(rt_{nxt_i}\) 时插入到 \(i\) 的位置。
对于 \(l,r\)：\(mx_i\) 即为 \(rt_{l+1}\) 到 \(rt_r\) 中存在值的最大下标，可以线段树上二分 \(O(\log n)\) 解决。
当然还有一种情况：\(y=x\)。
当然这是容易的，此时 \(mx_{nxt^3_i}\xleftarrow{\text{getmax}} i\)。我们记 \(nxt^k_x=nxt_{nxt^{k-1}_x},nxt^0_x=x\)。
总复杂度 \(O(n\log n)\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 5;
int n, a[N];
int rt[N];
struct sgt
{
int a[N << 5], ls[N << 5], rs[N << 5], idx;
void upd(int q, int l, int r, int x, int &u, int v)
{
u = ++idx;
a[u] = a[x], ls[u] = ls[x], rs[u] = rs[x];
if(l == r) return a[u] += v, void();
int mid = l + r >> 1;
if(mid >= q) upd(q, l, mid, ls[x], ls[u], v);
else upd(q, mid + 1, r, rs[x], rs[u], v);
a[u] = a[ls[u]] + a[rs[u]];
}
int fnd2(int l, int r, int x, int y)
{
if(l == r) return l;
int mid = l + r >> 1;
if(a[rs[x]] - a[rs[y]]) return fnd2(mid + 1, r, rs[x], rs[y]);
return fnd2(l, mid, ls[x], ls[y]);
}
int fnd(int ql, int qr, int l, int r, int x, int y)
{
if(ql > qr || ql > r || qr < l) return -1;
if(ql <= l && r <= qr)
{
if(a[x] == a[y]) return -1;
return fnd2(l, r, x, y);
}
int mid = l + r >> 1, ans;
if((ans = fnd(ql, qr, mid + 1, r, rs[x], rs[y])) == -1)
return fnd(ql, qr, l, mid, ls[x], ls[y]);
return ans;
}
}t;
int nxt[N], now[N];
int b[N], h = 0;
void init()
{
memcpy(b, a, sizeof b);
sort(b + 1, b + n + 1);
h = unique(b + 1, b + n + 1) - b - 1;
for(int i = 1; i <= n; i ++)
a[i] = lower_bound(b + 1, b + h + 1, a[i]) - b;
for(int i = n; i >= 1; i --)
if(!now[a[i]])
{
now[a[i]] = i;
nxt[i] = n + 1;
}
else
{
nxt[i] = now[a[i]];
now[a[i]] = i;
}
struct node {int id, p;} c[N];
for(int i = 1; i <= n; i ++)
c[i] = {i, nxt[i]};
sort(c + 1, c + n + 1, [](auto &x, auto &y) {return x.p < y.p;});
for(int i = 1, j = 1; i <= n && c[i].p <= n; i ++)
{
while(j < c[i].p) rt[j] = rt[j - 1], j ++;
t.upd(c[i].id, 1, n, rt[j - 1], rt[j], 1);
j ++;
}
}
int u[N], v[N], f[N], g[N], fr[N], id[N];
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
init();
for(int i = 1; i <= n; i ++)
{
if(!now[i]) continue;
int p = 0;
for(int r = nxt[now[i]], l = now[i]; r != n + 1; l = r, r = nxt[r], p = nxt[p])
{
int ans = t.fnd(1, l - 1, 1, n, rt[r - 1], rt[l]);
if(r == nxt[nxt[nxt[now[i]]]]) p = now[i];
if(ans != -1)
u[r] = ans, v[r] = r;
if(p && u[r] < p)
v[r] = r, u[r] = p;
}
}
for(int i = 1; i <= n; i ++)
{
if(u[i] < u[i - 1])
u[i] = u[i - 1], v[i] = v[i - 1];
if(u[i])
{
f[i] = g[u[i] - 1] + 4;
fr[i] = id[u[i] - 1];
}
if(f[i] > g[i - 1])
g[i] = f[i], id[i] = i;
else g[i] = g[i - 1], id[i] = id[i - 1];
}
cout << g[n] << "\n";
vector<int> ans;
for(int i = id[n]; i; i = fr[i])
{
ans.push_back(b[a[v[i]]]);
ans.push_back(b[a[u[i]]]);
ans.push_back(b[a[v[i]]]);
ans.push_back(b[a[u[i]]]);
}
reverse(ans.begin(), ans.end());
for(int i : ans) cout << i << " ";
return 0;
}