#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 1000010;
const ll  MAXN = 0x3f3f3f3f3f3f3f3f;

ll a[N];
struct node{
	int l, r;
	ll w, flag;
}tr[N * 4];

void up(int u){
	tr[u]. w = max(tr[u << 1]. w, tr[u << 1 | 1]. w);
	return;
}

void down(int u){
	if(tr[u]. flag){
		tr[u << 1]. w += tr[u]. flag;
		tr[u << 1 | 1]. w += tr[u]. flag;
		tr[u << 1]. flag += tr[u]. flag;
		tr[u << 1 | 1]. flag += tr[u]. flag;
		tr[u]. flag = 0;
	}
	return;
}

void build(int u, int l, int r){
	tr[u] = {l, r};
	if(l == r){
		tr[u]. w = -MAXN;
		return;
	}
	int mid = (l + r) >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
	up(u);
	return;
}
void change(int u, int l, int r, ll x){
	if(tr[u]. l >= l && tr[u]. r <= r){
		tr[u]. w += x;
		tr[u]. flag += x;
		return;
	}
	down(u);
	int mid = (tr[u]. l + tr[u]. r) >> 1;
	if(l <= mid)change(u << 1, l, r, x);
	if(r > mid)change(u <<  1 | 1, l, r, x);
	up(u);
	return;
}
void change_first(int u, int x){
	if(tr[u]. l == x && tr[u]. r == x){
		tr[u]. w = max(0ll, tr[u]. w);
		return;
	}
	down(u);
	int mid = (tr[u]. l + tr[u]. r) >> 1;
	if(x <= mid)change_first(u << 1, x);
	else change_first(u << 1 | 1, x);
	up(u);
	return; 
}
void change_one(int u, int x, ll w){
	if(tr[u]. l == x && tr[u]. r == x){
		tr[u]. w = max(tr[u]. w, w);
		return;
	}
	down(u);
	int mid = (tr[u]. l + tr[u]. r) >> 1;
	if(x <= mid)change_one(u << 1, x, w);
	else change_one(u << 1 | 1, x, w);
	up(u);
	return;
}

ll query(int u, int x){
	if(tr[u]. l == x && tr[u]. r == x){
		return tr[u]. w;
	}
	ll ans = 0;
	down(u);
	int mid = (tr[u]. l + tr[u]. r) >> 1;
	if(x <= mid)ans = query(u << 1, x);
	else ans = query(u << 1 | 1, x);
	up(u);
	return ans;
}

signed main(){
	int t;
	cin >> t;
	while(t --){
		memset(tr, 0, sizeof tr);
		int n;
		cin >> n;
		ll max_a = 0;
		for(int i = 1; i <= n; i ++){
			cin >> a[i];
			max_a = max(max_a, a[i]);
		}
		build(1, 1, max_a);
		change_first(1, a[1]);
		ll maxx = 0;
		for(int i = 2; i <= n; i ++){
			ll mid = query(1, a[i]) + a[i];
			if(a[i] == a[i - 1])change(1, 1, max_a, a[i]);
			change_one(1, a[i - 1], mid);
			change_first(1, a[i]);
			maxx = max(tr[1]. w, maxx);
		}
		cout << maxx << endl;
	}
	return 0;
}

思路见这里的65tps做法。