这是本人写的第一篇题解，有任何问题都欢迎和我说233

其实这道题本来是想作为22ak杯防ak题的，然而由于知识点对于新生太难就被lr580否决了

题意十分清晰，就是说是否对于全部区间[l, r]，它的最大值大于等于区间之和

第一反应想到的就是枚举l, r，很明显，对于2·10^5的数据量我们会超时

于是我们可以想到枚举每个点来作为最大值，那么就要维护每一个点左边第一个比它大的下标和右边第一个比它大的下标，这个就是单调栈

下面是左侧第一个小于的模板

//s是STL中的栈，pos[i]是左侧第一个小于a[i]的下标，a是原数组
for (int i = 0; i < n; i++)//方向，这里是左侧
{
    while (!s.empty() && !(a[s.top()] < a[i]))s.pop();
    //大小关系，这里是小于（非小于是因为要找到全部不满足a[s.top()]<a[i]的栈顶元素，将它们出栈）
    //当s为空说明左侧没有少于a[i]的元素
    if (s.empty())pos[i]=-1;//左侧的话就是-1，右侧的话就是n（实际上就是各边界刚好出界一个下标）
    else pos[i]=s.top();
    s.push(i);//记得将自己入栈
}

现在，我们维护好了对于每个点作为最大值之后的l_{max}，r_{min}，然而，对于每个点，直接检验[l_{max},r_{min}]并不能给我们正确答案，因为实际上最难满足不等式的[l_{ans},r_{ans}]会是[l_{max},r_{min}]的一个子集，而只有当最难满足的情况被满足了，我们才能说全部情况都满足

那么我们应该怎么找到最难满足不等式的[l_{ans},r_{ans}]呢？我们应该使不等式右侧的区间之和最大，那么这里就要用到新的算法/数据结构了，因为我们的时间复杂度最多为O(nlogn)，我们既不能慢慢一个一个求区间元素加和，也不能一个一个慢慢比较（都是O(n)），这样的话时间复杂度会达到O(n^3)

对于区间和，我们可以想到的是前缀和

for (int i = 1; i <= n; i++)
{
    pre[i] = pre[i - 1] + a[i];
}

对于前缀和求最值，我们就需要一个能求区间最值的数据结构

这里我选择了线段树（因为不会ST表）

在使用了前缀和后，区间和的形式是pre[r]-pre[l-1]。为了使这个公式最大化，我们就让pre[r]尽可能大，pre[l-1]尽可能小

实际上这里的l, r就是之前通过单调栈维护出的下标l_{max}，r_{min}

于是用数据结构来最大化和最小化即可

我的代码

/*
需要注意的事项：
1、这里是用pre来建树
2、这里需要判断front[i]是否等于-1（即前面不存在更小的值），如果等于，需要对minv取0与minv的最小值，因为建树是从1开始建的，会忽略前面的值，有可能存在什么都不取（即为0）而最小的情况，但不能直接赋为0，因为minv可能为负数，负数小于0
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long

int n;
int a[200005];
vector<int> pre;

struct node
{
    int l, r;
    int v;//最大值
    int v1;//最小值
}tr[4 * 200005];

void pushup(node& curr, node& left, node& right)
{
    curr.v = max(left.v, right.v);
    curr.v1 = min(left.v1, right.v1);
}

void pushup(int u)
{
    node left = tr[u << 1];
    node right = tr[u << 1 | 1];
    pushup(tr[u], left, right);
}

void build(int u, int l, int r)
{
    tr[u] = { l, r,pre[r],pre[r]};
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

node query(int u, int l, int r)
{
    if (l <= tr[u].l && r >= tr[u].r)return tr[u];
    int mid = tr[u].l + tr[u].r >> 1;
    if (r <= mid)return query(u << 1, l, r);
    else if (l > mid)return query(u << 1 | 1, l, r);
    else
    {
        node left = query(u << 1, l, r);
        node right = query(u << 1 | 1, l, r);
        node res;
        pushup(res, left, right);
        return res;
    }
}

void solve()
{
    pre.clear();
    
    cin >> n;
    pre.resize(n+1);
    for (int i = 1; i <= n; i++)cin >> a[i];
    vector<int> front(n+1);
    vector<int> back(n+1);
    for (int i = 1; i <= n; i++)
    {
        pre[i] = pre[i - 1] + a[i];
    }
    build(1, 1, n);
    stack<int> s;
    a[n+1]=INT_MAX;
    for (int i = 1; i <= n; i++)
    {
        while (!s.empty() && !(a[s.top()] > a[i]))s.pop();
        if (s.empty())front[i] = -1;
        else front[i] = s.top();
        s.push(i);
    }
    while (!s.empty())s.pop();
    for (int i = n; i >= 1; i--)
    {
        while (!s.empty() && !(a[s.top()] > a[i]))s.pop();
        if (s.empty())back[i] = n+1;
        else back[i] = s.top();
        s.push(i);
    }
    for (int i = 1; i <= n; i++)
    {
        int maxv = query(1, i, back[i]-1).v;
        int minv = query(1, front[i], i - 1).v1;
        if (front[i] == -1)minv = min(0ll, minv);
        if (a[i] >= maxv-minv)continue;
        cout << "NO\n";
        return;
    }
    cout << "YES\n";
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tt = 1;
    cin >> tt;
    while (tt--)solve();
    return 0;
}