毒瘤題

//Input Output
#include<iostream>
#include<fstream>
#include<sstream>
#include<streambuf>
//C lib
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<cctype>
//Container
#include<array>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<bitset>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
//Others
#include<tuple>
#include<algorithm>
#include<functional>
#include<numeric>
#include<iterator>
#include<limits>
#include<utility>
#include<complex>
#include<type_traits>
#include<initializer_list>

#if __cplusplus > 201703L
#include<concepts>
#endif

using namespace std;

#define debug(x) cout << #x << " : " << x << endl

namespace abb {
using ll = long long;
using ull = unsigned long long;
template<typename T> using V = vector<T>;
template<typename T> using Q = queue<T>;
template<typename T> using DQ = deque<T>;
template<typename T> using V2d = vector<vector<T>>;
template<typename T> using US = unordered_set<T>;
template<typename T, size_t s> using A = array<T, s>;
template<typename T1, typename T2> using UM = unordered_map<T1, T2>;
template<typename T1, typename T2 = T1> using P = pair<T1, T2>;
template<typename T, typename Cmp = less<T>> using S = set<T, Cmp>;
template<typename T, typename Cmp = less<T>> using PQ = priority_queue<T, Cmp>;
template<typename T1, typename T2, typename Cmp = less<T1>> using M = map<T1, T2, Cmp>;
}

namespace output {
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    for (const auto& i : v) os << i << ' ';
    return os;
}
template<typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
    return os << '(' << p.first << ", " << p.second << ')';
}
template<typename T>
ostream& operator<<(ostream& os, const set<T>& s) {
    for (const auto& i : s) os << i << ' ';
    return os;
}
template<typename T1, typename T2>
ostream& operator<<(ostream& os, const map<T1, T2>& m) {
    for (const auto& i : m) os << i << ' ';
    return os;
}
};

namespace rit {
struct fast_istream {
    operator bool() const {return bool(cin);}
    fast_istream() {cin.tie(nullptr);}
} fin;
#if __cplusplus > 201703L
template<typename T>
fast_istream& operator>>(fast_istream& is, T& n) requires integral<T> {
#else
template<typename T, class = typename enable_if<is_integral<T>::value>::type>
fast_istream & operator>>(fast_istream& is, T& n) {
#endif
    while (isspace(cin.rdbuf()->sgetc()))
        cin.rdbuf()->snextc();
    bool sign = false;
    if (cin.rdbuf()->sgetc() == '-')
        sign = true, cin.rdbuf()->snextc();
    for (n = 0; isdigit(cin.rdbuf()->sgetc());)
        n *= 10, n += cin.rdbuf()->sbumpc() - '0';
    n = sign ? -n : n;
    return is;
}
fast_istream& operator>>(fast_istream& is, char& n) {
    while (isspace(cin.rdbuf()->sgetc()))
        cin.rdbuf()->snextc();
    n = cin.rdbuf()->sbumpc();
    return is;
}
}

#define endl '\n'
namespace wit {
struct fast_ostream {
    operator bool() const {return bool(cout);}
    fast_ostream() {cout.tie(nullptr);}
} fout;
constexpr int buffer_size = 30;
#if __cplusplus > 201703L
template<typename T>
fast_ostream& operator<<(fast_ostream& os, T n) requires integral<T> {
#else
template<typename T, class = typename enable_if<is_integral<T>::value>::type>
fast_ostream & operator<<(fast_ostream& os, T n) {
#endif
    if (!n) {cout.rdbuf()->sputc('0'); return os;}
    if (n < 0) cout.rdbuf()->sputc('-'), n = -n;
    static char buffer[buffer_size];
    int cnt = buffer_size;
    for (; n; n /= 10)
        buffer[--cnt] = n % 10 + '0';
    cout.rdbuf()->sputn(buffer + cnt, buffer_size - cnt);
    return os;
}
fast_ostream& operator<< (fast_ostream& os, const char& n) {
    cout.rdbuf()->sputc(n); return os;
}
}

#define MULTI_TASKCASE
using namespace abb;
using namespace output;
using namespace rit;
using namespace wit;

inline void init() {

}


inline void c1() {
    ll n, k, maxn = -1e9, curn = -1e9; cin >> n;
    while (n--)
        cin >> k, curn = max(0LL, curn) - k, maxn = max(maxn, curn);
    cout << maxn << endl;
}

V<int> v; int n;
int ans = 0, cura = 0, curb = 0;
void dfs(int i) {
    if (i == n) {ans = max(ans, cura * curb); return;}
    cura += v[i], dfs(i + 1), cura -= v[i];
    curb += v[i], dfs(i + 1), curb -= v[i];
}

inline void c2() {
    int curn = -1e9, maxn = -1e9; cin >> n;
    v.resize(n);
    for (auto& i : v)
        fin >> i, curn = max(0, curn) - i, maxn = max(maxn, curn), i = maxn;
    // debug(v);
    dfs(0);
    fout << ans << endl;
}

function<void()> solve[] = {c1, c2};
//#define FILEIO
main() {
    ios::sync_with_stdio(false);
#ifdef FILEIO
    fstream filein("in.txt", ios::in);
    fstream fileout("out.txt", ios::out);
    cin.rdbuf(filein.rdbuf());
    cout.rdbuf(fileout.rdbuf());
#endif
    init();
    int t = 1, c;
#ifdef MULTI_TASKCASE
    cin >> c >> t;
#endif
    while (t--) solve[c == 2]();
    return 0;
}