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

int main() {
    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        vector<ll> A(N);
        for (int i = 0; i < N; ++i) cin >> A[i];

        // 累積和を構築
        vector<ll> S(N + 1, 0);
        for (int i = 0; i < N; ++i) {
            S[i + 1] = S[i] + A[i];
        }

        ll ans = LLONG_MIN;
        ll max_prefix = LLONG_MIN;

        // jを2からN-1まで動かす
        for (int j = 2; j < N; ++j) {
            // i = j-1 に固定して、|S_i| + |S_j - S_i| を計算して最大値を更新
            ll cur = abs(S[j - 1]) + abs(S[j] - S[j - 1]);
            max_prefix = max(max_prefix, cur);

            // 第3項 |S_N - S_j| を加算してスコアを計算
            ll score = max_prefix + abs(S[N] - S[j]);
            ans = max(ans, score);
        }

        cout << ans << '\n';
    }
    return 0;
}