sparse table template AK

/***
 created: 2022-08-07-23.28.09
***/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define int ll
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'

const ll lim=200005;
const ll inf=-2e18;

int a[lim],psum[lim],ssum[lim];

struct Sparse
{
    int n,lg;
    vector<vector<int> >sparse_mx,sparse_mn;
    vector<int>A;
    void init(int tmp)
    {
        n=tmp;
        A.resize(n+3);
        lg=32-__builtin_clz(n+2);// 64 if nmx > 10^9
        sparse_mx=vector< vector<int> >(n+2,vector<int>(lg));

    }
    void abr_init(int aa[])
    {
        for(int i=1; i<=n; i++)A[i]=aa[i];
        build_table();
    }
    void build_table()
    {
        for(int i=1; i<=n; i++)sparse_mx[i][0]=A[i];
        for(int k=1,p=1; k<lg; k++,p<<=1)
        {
            for(int i=1; i+p+p<=n+1; i++)
            {
                sparse_mx[i][k]=max(sparse_mx[i][k-1],sparse_mx[i+p][k-1]);

            }
        }
    }
    int qmx(int l,int r)
    {
        int len=r-l+1;
        int k=32-__builtin_clz(len)-1;
        return max(sparse_mx[l][k],sparse_mx[r-(1<<k)+1][k]);
    }



};


main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    test
    {
        ll n,m,i,j,k,l,ans=0;

        Sparse sa,sp,ss;

        cin>>n;

        for(i=1; i<=n; i++) cin>>a[i];

        k=0;

        for(i=1;i<=n;i++)
        {
            k+=a[i];
            psum[i]=k;
        }

        k=0;

        for(i=n;i>=1;i--)
        {
            k+=a[i];
            ssum[i]=k;
        }

        ssum[n+1]=0;

        sa.init(n);
        sa.abr_init(a);
        sp.init(n);
        sp.abr_init(psum);
        ss.init(n);
        ss.abr_init(ssum);


        for(i=1; i<=n; i++)
        {
            ll lo=1,hi=i;

            while(lo<hi)
            {
                ll mid=(lo+hi)/2;

                ll mx=sa.qmx(mid,i);

                if(mx<=a[i])
                {
                    hi=mid;
                }
                else lo=mid+1;
            }

            ll lft=hi;

            lo=i,hi=n;

            while(lo<hi)
            {
                ll mid=(lo+hi+1)/2;

                ll mx=sa.qmx(i,mid);

                if(mx<=a[i])
                {
                    lo=mid;
                }
                else hi=mid-1;
            }

            ll rgt=lo;

            ll rtmx = sp.qmx(i,rgt)-psum[i-1];
            ll lfmx = ss.qmx(lft,i)-ssum[i+1];

            ll z=rtmx+lfmx-a[i];

            if(z>a[i])
            {
                ans=1;
                break;
            }

        }

        if(ans==0) cout<<"YES"<<nl;
        else cout<<"NO"<<nl;

    }

    get_lost_idiot;
}