/*
f[i][x][y] 表示对于前i个位置，上一个染色红色的x，染色蓝色的是y
此时得分的最大值
转移：f[x][i] = max(f[x][i - 1] + (a[i] == a[i - 1])*a[i])
f[i][x] = max(f[i - 1][x] + (a[i] == a[i - 1])*a[i]) 
f[i - 1][i] = max(f[i - 1][x] + (a[i] == a[x])*a[i])
f[i][i - 1] = max(f[x][i - 1] + (a[i] == a[x])*a[i])
x 从 0 枚举到 i - 2

蓝色和红色是对称
f[x][i] = max(f[x][i - 1] + (a[i] == a[i - 1])*a[i])
f[i - 1][i] = max(f[i - 1][x] + (a[i] == a[x])*a[i])

除非a[i] == a[i - 1], 
对于长度>=2的相同的a[i]段的情况，对于所有i，答案都在对角线旁边
先处理不存在长度>=2的相同a[i]的情况。
f[i][j] = f[i][j + 1] (j > i)
f[i - 1][i] = max(f[x][i - 1] + (a[i] == a[x]) * a[i])
f[i - 1] = max(f[x] + (a[i] == a[x])*a[i])
*/

// void solve1()
// {
//     memset(f, 0, sizeof f);
//     cin >> n;
//     for(int i = 1; i <= n; i++) cin >> a[i];

//     for(int i = 1; i <= n; i++)
//         for(int x = 0; x <= i - 2; x++)
//             f[i - 1] = max(f[i - 1], f[x] + (a[i]==a[x])*a[i]);
// }
/*
长度>=2的相同a[i]段的情况：
    f[i] = f[i][j];  (i < j <= n)
    f[i][j + 1] = f[i][j] + a[i];
    f[j] = f[j] + a[i]

*/
// #include<bits/stdc++.h>
// using namespace std;

// typedef long long LL;
// const int N = 2e5 + 10;
// int n, a[N];
// LL f[N];
// void solve2()
// {
//     memset(f, 0, sizeof f);
//     cin >> n;
//     for(int i = 1; i <= n; i++) cin >> a[i];

//     for(int i = 1; i <= n; i++) {
//         for(int x = 0; x <= i - 2; x++)
//             f[i - 1] = max(f[i - 1], f[x] + (a[i]==a[x])*a[i]);

//         if(a[i] == a[i - 1])
//                 for(int j = 0; j <= i - 2; j++)
//                     f[j] += a[i];
//     }

//     cout << *max_element(f, f + n) << endl;
    
// }

// int main()
// {
//     int t ;
//     cin >> t;
//     while(t --)
//     {
//         solve2();
//     }
// }

/*
f[i - 1] = max(max(f[j]), max(f[j] + a[i]));
考虑用桶优化，记录f[j]的最大值和a[j] = C的f[j]的最大值，直接转移
*/

// #include<bits/stdc++.h>
// using namespace std;

// typedef long long LL;
// const int N = 2e5 + 10, M = 1e6 + 20;
// int n, a[N];
// LL f[N], premax, last[M], ans;

// struct BIT{
//     LL tr[N];
//     void init(){
//         memset(tr, 0, sizeof tr);
//     }

//     int lowbit(int x)
//     {
//         return x & -x;
//     }
//     void add(int a, int b)
//     {
//         for(int i = a; i <= n; i += lowbit(i))
//             tr[i] += b;
//     }
//     void add(int l, int r, LL v)
//     {
//         add(l, v), add(r + 1, -v);
//     }

//     LL query(int p)
//     {
//         LL res = 0;
//         for(int i = p; i; i -= lowbit(i))
//             res += tr[i];

//         return res;
//     }
// } t;

// void solve2()
// {
//     memset(f, 0, sizeof f);
//     cin >> n;
//     t.init();
//     for(int i = 1; i <= n; i++) cin >> a[i], last[a[i]] = 0;
//     premax = ans = 0;

//     for(int i = 2; i <= n; i++)
//     {
//         f[i - 1] = max(premax, last[a[i]]?f[last[a[i]]] + t.query(last[a[i]] + 1)+a[i]:0);
//         if(a[i] == a[i - 1])
//         {
//             premax += a[i];
//             t.add(1, i - 1, a[i]);
//         }
//         premax = max(premax, f[i - 1]);
//         if(last[a[i - 1]] == 0 || f[i - 1] > f[last[a[i - 1]]] + t.query(last[a[i - 1]] + 1))
//             last[a[i - 1]] = i - 1;
//     }
    
//     cout << premax << endl;
    
// }

// int main()
// {
//     int t ;
//     cin >> t;
//     while(t --)
//     {
//         solve2();
//     }
// }
/*
前缀和优化
*/

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 2e5 + 10, M = 1e6 + 20;
int n, a[N];
LL f[N], pre[M], idx[M], s[N];


void solve2()
{
    cin >> n;
    memset(idx, -1, sizeof idx);
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        pre[i] = idx[a[i]];
        idx[a[i]] = i;
    }
    for(int i = 1; i <= n; i++)
    {
        s[i] = s[i - 1];
        if(a[i] == a[i - 1])
            s[i] += a[i];
    }
    for(int i = 1; i <= n; i++)
    {
        f[i] = f[i - 1];
        if(~pre[i])
        {
            f[i] = max(f[i], f[pre[i] + 1] + a[i] + s[i - 1] - s[pre[i]]);
        }
    }
    cout << f[n] << endl;
}

int main()
{
    int t ;
    cin >> t;
    while(t --)
    {
        solve2();
    }
}
···