#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long int
const int MOD = 1000000007;
const int MOD2 = 998244353;
const int INF = LLONG_MAX / 2;
const int MAXN = 100000;
int primes[1000000];
 
/*void seive() {
    fill(primes, primes + 1000000, 1);
    primes[0] = primes[1] = 0;
    for (int i = 2; i * i < 1000000; i++) {
        if (primes[i]) {
            for (int j = i * i; j < 1000000; j += i) {
                primes[j] = 0;
            }
        }
    }
}
 
bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}
 
int gcd(int a, int b) {
    if (a == 0) return b;
    return gcd(b % a, a);
}
 
int power(int a, int b, int mod) {
    int res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
 
// nCr % MOD for n < MOD
int nCrModP(int n, int r) {
    if (r > n) return 0;
    if (r == 0 || r == n) return 1;
 
    int numerator = 1, denominator = 1;
    for (int i = 0; i < r; i++) {
        numerator = (numerator * (n - i)) % MOD;
        denominator = (denominator * (i + 1)) % MOD;
    }
    return (numerator * power(denominator, MOD - 2, MOD)) % MOD;
}
 
// Lucas's Theorem
int lucas(int n, int r) {
    if (r == 0) return 1;
    return (lucas(n / MOD, r / MOD) * nCrModP(n % MOD, r % MOD)) % MOD;
}*/
void solve() {
    int n;
    cin>>n;
    int A[n];
    int total = 0;
    for(int i = 0 ; i<n ; i++){
        cin>>A[i];
        total += A[i];
    }
    int p4[n],p2[n];
    p4[n-1] = A[n-1];
    int sum = A[n-1];
    for(int i = n-2 ; i>=0 ; i--){
        sum += A[i];
        p4[i] = min((p4[i+1]),sum);
    }
    sum = 0;
    for(int i = 0 ; i<n ; i++){
        p2[i] = min(A[i],(sum+A[i]));
    }
    int ans = LLONG_MAX;
    ans = min(p2[n-1],p4[0]);
    for(int i = 0 ; i<n-1 ; i++){
        int d = min(0LL,p2[i])+min(0LL,p4[i+1]);
        ans = min(ans,d);
    }
    cout<<total-(2*ans)<<endl;
}
signed main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}