枚举有 $x$ 个子序列是 $\texttt{1,2,3}$, $y$ 个是 $\texttt{3,2,1}$。
然后显然的贪心是 $x$ 中选择的 $\texttt1$ 是前 $x$ 个 $\texttt{1}$，$\texttt{3}$ 是后 $x$ 个 $\texttt{3}$，且 $\texttt{1,3}$ 之间按照顺序匹配。$y$ 同理。
现在构成了一个 点-线段 的匹配模型。由经典 Hall 定理套路，有完美匹配当且仅当：枚举所有 $l,r$，完全包含在 $[l,r]$ 内的线段条数 $\leq$ $[l,r]$ 内的点数。
注意：枚举 $[l,r]$ 然后要求 $[l,r]$ 内的点数 $\leq$ 与 $[l,r]$ 有交的线段数是错误的！
发现可以用较为简洁的方式表示出来 $[l,r]$ 内的线段条数。设 $cnt(x,l,r)$ 表示 $a_{[l,r]}$ 内有多少个 $x$，那么：
- 形如 $\texttt{1,3}$ 的线段有 $A=\max(0, x-cnt(3,r+1,n)-cnt(1,1,l-1))$；
- 形如 $\texttt{3,1}$ 的线段有 $B=\max(0, x-cnt(1,r+1,n)-cnt(3,1,l-1))$；
- 要求是 $A+B\leq \min\{cnt(1,1,n),cnt(2,l,r),cnt(3,1,n)\}$。
拆 $\max$，可以算出 $x,y,x+y$ 分别的上界。
构造是简单的，贪心即可。