rt，本人考场上乱想打了个暴力，没想到大样例没T。

思路好像有点类似正解了，用f记录当下的最优解。

转移到前一个 $a[i]$ 出现的位置的后一个，然后暴力 $O(n)$ 计算中间全涂异色的贡献。

因为显然后面的那个数不等于前面的，所以把两色染成异色一定不劣，且由于红蓝颜色对称，所以可以少考虑一些细节。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define F(a,b,c)  for(int a=b ; a<=c ; a++)
#define Fe(a,b,c) for(int a=b ; a>=c ; a--)
#define int long long
#define db double

const int LXB = 2e6+5;
const int lxb = 3e3+5;
const int INF = 999999999;
const int mod = 998244353;



int n,m;
int a[LXB];
int f[LXB];
int last[LXB];

int calc(int l, int r)
{
    int res=0;
    F(i,l+1,r) if (a[i-1]==a[i]) res+=a[i];
    return res; 
}

void init()
{
    memset(last,0,sizeof(last));
    memset(f,0,sizeof(f));
}

void solve()
{
    init();
    cin>>n;
    F(i,1,n) cin>>a[i];
    F(i,1,n) {
        f[i]=f[i-1];
        if (last[a[i]]) f[i] = max(f[i-1], f[last[a[i]]+1]+calc(last[a[i]]+1, i)+a[i]);
        last[a[i]] = i;
    }
    cout<<f[n]<<endl;
}



signed main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

民间数据能过75分的点……到底是因为数字总量比较小，所以跳位置比较方便，还是因为数据比较水的原因……

不过想来CCF应该也严谨不到哪里去……