定义一个正整数序列 $\{b_1,b_2,\cdots,b_m\}$ 为 1122 数列 当且仅当序列满足以下所有条件：

给出长度为 $n$ 的序列 $a$，求出 $a$ 的（可以不连续）子序列中，是 1122 数列 的序列的长度最大值。

比较简单的状压 dp，还好场切了。

假设我们现在尝试构造一个合法序列。称 $a_i$ 的值为颜色，用一次颜色 $x$ 表示将两个满足 $a_i=x$ 的不同下标加入序列末尾。由条件 3 每种颜色至多会被使用一次。同时我们每次往序列末尾添加某个颜色，只关注用过的最大下标（即加入颜色前序列末尾的下标），以及哪些颜色已经被用过，而由于颜色数 $m\le 20$，把这个信息记录下来是可行的。

考虑大概按照这个每次向序列末尾添加一个颜色的过程 dp，把我们关注的两样东西记入状态：记 $f(i,S)=0/1$ 表示顺次考虑到末尾下标为 $i$ 的序列，使用颜色的集合为 $S$ 是否可行（注意到序列长度即 $2|S|$，不用记录什么“最大长度”）。转移枚举一个没用过的颜色 $x$ 加到末尾，贪心地选取 $i$ 之后最近的两个下标 $j,k$ 且 $j<k,a_j=a_k=x$，转移到 $f(k,S\cup\{x\})$。状态数 $O(n2^m)$。

考虑优化状态。实际上你往一个前面已经决定好的序列末尾加入一个颜色，只关心的是颜色的集合，这些用过的颜色怎么排列是不重要的。而且 bool 的状态太浪费了，完全可以把 $i$ 扔进状态对应的值里面去，即对同样颜色集合构成的序列只取末尾最靠前的转移。此时状态变为 $f_S$，表示使用颜色集合为 $S$ 的合法序列，序列末尾下标的最小值。转移类似枚举 $x$，取最前的两个下标 $j,k$ 满足 $f_S<j<k,a_j=a_k=x$，更新 $f_{S\cup \{x\}} \to \min(f_{S\cup \{x\}},k)$。

最终 $ans=\max\limits_{f_S\le n}|S|$，时间复杂度 $O(m2^m\log n)$，对数来自二分求 $j,k$。