笑点解析：区修区查线段树，$n \le 2000$ 做了 $n$ 次 memset 2e5 long long，选前四个同色点转移然后 u = pre[i] 实际只取了一个点，然后高达六倍常数的线段树冲过了 2e6。

#include <bits/stdc++.h>
#define X first
#define Y second
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, a, b) for (int i = a; i >= b; i--)
using namespace std;
typedef long long int ll;
using pii = pair<int, int>;
const int maxn = 2e5 + 10, mod = 998244353;
int T, n, a[maxn]; ll f[2][maxn], c[maxn]; 
struct Node { ll mx, tg; } t[maxn << 2]; 
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define mx(x) (t[x].mx)
#define tg(x) (t[x].tg)
#define mid (l + r >> 1)
inline void up(int x) { mx(x) = max(mx(ls(x)), mx(rs(x))); }
inline void down(int x) { 
	if (tg(x)) {
		mx(ls(x)) += tg(x), tg(ls(x)) += tg(x);
		mx(rs(x)) += tg(x), tg(rs(x)) += tg(x);
		tg(x) = 0;
	}
}
void add(int l, int r, int ml, int mr, int v, int x) {
	if (ml <= l && r <= mr) return mx(x) += v, tg(x) += v, void(); down(x);
	ml <= mid && (add(l, mid, ml, mr, v, ls(x)), 0); mr > mid && (add(mid + 1, r, ml, mr, v, rs(x)), 0); up(x);
}
void mdf(int l, int r, int v, ll k, int x) {
	if (l == r) return mx(x) = tg(x) = k, void(); down(x);
	v <= mid ? mdf(l, mid, v, k, ls(x)) : mdf(mid + 1, r, v, k, rs(x)); up(x); 
}
ll qry(int l, int r, int v, int x) {
	if (!v) return 0;
	if (l == r) return mx(x); down(x);
	return v <= mid ? qry(l, mid, v, ls(x)) : qry(mid + 1, r, v, rs(x));
}
int pre[maxn], b[maxn * 5];
int main() {
	freopen("color.in", "r", stdin);
	freopen("color.out", "w", stdout);
	scanf("%d", &T);
	while (T--) {
		memset(t, 0, sizeof(t));
		scanf("%d", &n);
		//if (n > 2000) break;
		rep(i, 1, n) scanf("%d", &a[i]), pre[i] = b[a[i]], b[a[i]] = i;
		rep(i, 1, n) b[a[i]] = 0;
		if (n <= 2000) {
			memset(f, 0, sizeof(f)); int c = 0;  
			rep(i, 1, n) {
				memset(f[c ^ 1], 0, sizeof(f[c ^ 1]));
				rep(j, 1, i) {
					f[c ^ 1][j] = f[c][j - 1] + (a[i] == a[i - 1] ? a[i] : 0);
					ll w = (a[i - j] == a[i] ? a[i] : 0); 
					f[c ^ 1][1] = max(f[c ^ 1][1], f[c][j - 1] + w);
				}
				c ^= 1;
			}
			ll ans = 0;
			rep(i, 1, n) ans = max(ans, f[c][i]);
			printf("%lld\n", ans);
		} 
		else {
		//now 全局加标记 
			rep(i, 1, n) { 
				ll w = mx(1);
				int qwq = 4, u = pre[i];
				while (u && qwq) {
					//u = i - j
					w = max(w, qry(1, n, n - u, 1) + a[i]);
					u = pre[i], --qwq;
				}
				if (a[i] == a[i - 1]) add(1, n, n - i + 1, n, a[i], 1);
				if (w > qry(1, n, n - i + 1, 1)) mdf(1, n, n - i + 1, w, 1);
			}
			printf("%lld\n", mx(1));
		}
	}
	return 0;
}