#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long
 
int main()
{
	int tests, n;
 
	cin >> tests;
 
	while (tests--)
	{
		cin >> n;
 
		vector <ll> a(n + 1), dp(n + 1), dp_with_delete(n + 1);
 
		ll mx = INT_MIN;
 
		for (int i = 1; i <= n; i++)
		{
			cin >> a[i];
 
			dp[i] = max(dp[i - 1] + a[i], a[i]);
 
			mx = max(mx, dp[i]);
		}
 
		for (int i = 2; i <= n; i++)
		{
			dp_with_delete[i] = max(dp_with_delete[i - 1] + a[i], dp[i - 1]);
 
			mx = max(mx, dp_with_delete[i]);
		}
 
		cout << mx <<"\n";
	}
}

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIGxsIGxvbmcgbG9uZwoKaW50IG1haW4oKQp7CglpbnQgdGVzdHMsIG47CgoJY2luID4+IHRlc3RzOwoKCXdoaWxlICh0ZXN0cy0tKQoJewoJCWNpbiA+PiBuOwoKCQl2ZWN0b3IgPGxsPiBhKG4gKyAxKSwgZHAobiArIDEpLCBkcF93aXRoX2RlbGV0ZShuICsgMSk7CgoJCWxsIG14ID0gSU5UX01JTjsKCgkJZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKQoJCXsKCQkJY2luID4+IGFbaV07CgoJCQlkcFtpXSA9IG1heChkcFtpIC0gMV0gKyBhW2ldLCBhW2ldKTsKCgkJCW14ID0gbWF4KG14LCBkcFtpXSk7CgkJfQoKCQlmb3IgKGludCBpID0gMjsgaSA8PSBuOyBpKyspCgkJewoJCQlkcF93aXRoX2RlbGV0ZVtpXSA9IG1heChkcF93aXRoX2RlbGV0ZVtpIC0gMV0gKyBhW2ldLCBkcFtpIC0gMV0pOwoKCQkJbXggPSBtYXgobXgsIGRwX3dpdGhfZGVsZXRlW2ldKTsKCQl9CgoJCWNvdXQgPDwgbXggPDwiXG4iOwoJfQp9

Mgo1CjEgLTIgMyAtMiA1CjIKLTEgLTI=

2
5
1 -2 3 -2 5
2
-1 -2