定义集合\(S\)由同时满足以下条件的\(x\)构成：
- \([1,x)\)中\(\le a_{x}\)的元素 和 \((x,n]\)中\(\ge a_{x}\)的元素 构成递增子序列
- \([1,x)\)中\(\ge a_{x}\)的元素 和 \((x,n]\)中\(\le a_{x}\)的元素 构成递减子序列
性质1：\(a\)为完美数组当且仅当\(S\ne \empty\)
必要性：注意\(x\in S\)是\(x\)可以染成红色和绿色的必要条件
充分性：任取\(x\in S\)，将条件中第\(1\)类元素染成红色，其余染成绿色即可
性质2：若\(x\in S\)，则\(x+1\in S\iff \forall i\in [1,x),a_{i}\not\in [a_{x},a_{y}]\cup [a_{y},a_{x}]\)
性质3：记\(\begin{cases}l=\min_{x\in S}x\\r=\max_{x\in S}x\end{cases}\)，则\(S=[l,r]\cap Z\)且满足以下条件之一
- \(l+1=r\)且\(a_{l}=a_{r}\)
- \(a_{l}<a_{l+1}<...<a_{r}\)或\(a_{l}>a_{l+1}>...>a_{r}\)
（证明可以自行分类讨论得到）
为了方便，以下均假设为第\(2\)种情况，第\(1\)种情况是类似的
根据性质\(3\)，在\(r\)处统计方案数，即要求\(r+1\not\in S\)，这可以用性质\(2\)判定
注意到对于\(a_{[1,r)}\)，恰存在一种染色方式使得红色的结尾\(<a_{r}\)且绿色的结尾\(>a_{r}\)
定义\(f_{i,x,y}\)表示前\(i\)个位置中两序列结尾分别为\(x,y\)的方案数，转移易优化至\(O(nm^{2})\)，后缀类似
枚举\(r,a_{r}\)和\(a_{r+1}\)后，即求形如\(\sum_{x\le x_{0}}\sum_{y\ge y_{0}}f_{i,x,y}\)，预处理即可，时间复杂度为\(O(tnm^{2})\)
性质4：得分最大的染色方案形如
- \([1,r)\)中\(\le a_{r}\)的元素 和 \((r,n]\)中\(\ge a_{r}\)的元素 染成红色
- \([1,r)\)中\(\ge a_{r}\)的元素 和 \((r,n]\)中\(\le a_{r}\)的元素 染成绿色
- \(a_{r}\)的颜色取染红色或绿色中的较大值
此时，将贡献拆开，得分分为以下几部分：
-
\(a_{[1,r)}\)中，用\(g/g0/g1_{i,x,y}\)表示……的得分和、红色数和 和 绿色数和 即可
-
\(a_{r}\)中，用\(f'_{i,z,x,y}\)表示在\(f_{i,x,y}\)的基础上红色有\(z\)个的方案数即可
-
\(a_{(r,n]}\)中，其内部无贡献，仅与\(a_{[1,r)}\)之间有贡献
以染成红色的\(a_{i}\)为例，即统计\(a_{[1,r)}\)中\(>a_{i}\)的元素个数，枚举\(a_{i}\)即可
时间复杂度为\(O(tn^{2}m^{2}+tnm^{3})\)，需要一定卡常