不知道对不对，大样例过了，即使错了也可能能骗点分
先读入时将多个相邻的同一个数压成一个并统计这些重复数的答案，且预处理出 $pre[i]$：$i$ 左侧离 $i$ 最近的和 $i$ 相同的数的下标。
令dp数组 $f[i]$ 表示强制让第 $i$ 个数满足要求被选，由于第一步已经去重所以区间 $(pre[i],i)$ 内的异色不存在可互相匹配的情况，然后发现有3种转移：
1.由 $f[1...pre[i]-1]$ 转移而来，可以理解为直接拼上去。
2.由 $f[pre[i]]$ 转移而来，此时 $i$ 应取同色。
3.由 $f[pre[i]+1]$ 转移而来，此时对应 $pre[i]$ 被横跨的情况（也只有这一种了，横跨的右端点只能是 $pre[i]+1$），$i$ 应取异色。
将三种情况合起来发现 $f[i]$ 是直接由 $f[1...pre[i]+1]$ 转移过来，然后记个 $f$ 的前缀最大值即可优化至线性复杂度。即最后的转移式： $f[i]=premax[pre[i]+1]+a[i]$ 答案即为 $premax[n]+tot$（$tot$ 为之前算相邻重复数字时统计的贡献值）。
有可能有些没考虑到的情况或是多算的情况，因本人能力有限无法举出，希望各位大佬能够指正。
当时考场T2耗太久了于是随便乱糊的思路没想到过大样例了，当时我写的T3代码还不到T2一半，没写对拍反正即使拍出来发现自己错了也想不出正解