G Removing Stones

比赛的时候被的特判卡的太久了，都没有看这个题，赛后想了一会儿发现这个题和上某场的E十分相似。这个题能胜利的区间应该满足一个比较特殊的性质，我们设这个区间的最大指为，那么只有当区间的和大于的两倍时，这个区间才是满足胜利性质的条件。

我们考虑分治做法，当我们枚举一个区间到时，我们先找到区间最大值的位置，然后我们设满足答案的区间是包含这个最大值的，因此我们只需要固定一个左端点或者右端点，然后二分去查找另外一个端点的位置，就能统计答案了，这个做法实际上是十分的显然。接下来，我们先设最大值的位置为，因为我们已经处理了这个最大值所能影响的区间，接下来我们只需要解决不包含这个最大值的区间我们就能得到子区间的答案，具体来说就是分治的处理和两个区间。

值得注意的是，当我们查找最大值时，最好不要用线段树或者直接买枚举的做法，反正我是了，正确做法是用表预处理一个区间的最大值位置，然后去查询就好了。这个题有许多的细节问题，看看代码就知道了。

//author Forsaken
#define Hello the_cruel_world!
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<utility>
#include<cmath>
#include<climits>
#include<deque>
#include<functional>
#include<numeric>
#define lowbit(x) ((x) & (-(x)))
#define FRIN freopen("std.in", "r", stdin)
#define FROUT freopen("std.out", "w", stdout)
#define FAST ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define outd(x) printf("%d\n", x)
#define outld(x) printf("%lld\n", x)
#define memset0(arr) memset(arr, 0, sizeof(arr))
#define il inline
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int maxn = 3e5;
const int INF = 0x7fffffff;
const int mod = 1e9 + 7;
const double eps = 1e-7;
const double Pi = acos(-1.0);
il int read_int() {
    char c;
    int ret = 0, sgn = 1;
    do { c = getchar(); } while ((c < '0' || c > '9') && c != '-');
    if (c == '-') sgn = -1; else ret = c - '0';
    while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0');
    return sgn * ret;
}
il ll read_ll() {
    char c;
    ll ret = 0, sgn = 1;
    do { c = getchar(); } while ((c < '0' || c > '9') && c != '-');
    if (c == '-') sgn = -1; else ret = c - '0';
    while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0');
    return sgn * ret;
}
il ll quick_pow(ll base, ll index, ll p) {
    ll res = 1;
    while (index) {
        if (index & 1)res = res * base % p;
        base = base * base % p;
        index >>= 1;
    }
    return res;
}
int arr[maxn + 5], n, t;
ll sum[maxn + 5], res;
int st[maxn + 5][20];
void init() {
    for (int i = 1; i <= n; ++i) st[i][0] = i;
    for (int j = 1; j <= 19; ++j)
        for (int i = 1; i + (1 << j) - 1 <= n; ++i)
            st[i][j] = arr[st[i][j - 1]] > arr[st[i + (1 << (j - 1))][j - 1]] ? st[i][j - 1] : st[i + (1 << (j - 1))][j - 1];
}
int query(int l, int r) {
    int k = log2(r - l + 1);
    return arr[st[l][k]] > arr[st[r - (1 << k) + 1][k]] ? st[l][k] : st[r - (1 << k) + 1][k];
}
void solve(int l, int r) {
    if (r - l + 1 <= 1) return;
    if (r - l + 1 == 2) {
        if (arr[l] == arr[r])++res;
        return;
    }
    int k = -1, v = -1;
    k = query(l, r), v = arr[k];
    if (k - l < r - k) {
        for (int i = l; i <= k; ++i) {
            ll s = sum[i - 1] + 2ll * v;
            int pos = -1;
            if (sum[r] < s)pos = r + 1;
            else if (sum[k] >= s)pos = k;
            else pos = lower_bound(sum + 1, sum + 1 + n, s) - sum;
            res += r - pos + 1;
        }
    }
    else {
        for (int i = k; i <= r; ++i) {
            ll s = sum[i] - 2ll * v;
            int pos = -1;
            if (sum[l - 1] > s)pos = l - 1;
            else if (sum[k - 1] <= s)pos = k;
            else pos = upper_bound(sum + 1, sum + 1 + n, s) - sum;
            res += pos - l + 1;
        }
    }
    solve(l, k - 1);
    solve(k + 1, r);
}
int main()
{
    t = read_int();
    while (t--) {
        n = read_int();
        res = 0;
        for (int i = 1; i <= n; ++i) {
            arr[i] = read_int();
            sum[i] = sum[i - 1] + arr[i];
        }
        init();
        solve(1, n);
        outld(res);
    }
    //system("pause");
    return 0;
}