Untitled

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

bool doesChainExists(vector<int> &nums) {
    int n=nums.size();
    vector<int> preffSum(n,0), suffSum(n,0);
    unordered_map<int,int> mpSuff, mpPref;
    preffSum[0]=nums[0];
    mpPref[preffSum[0]]=0;
    /** We are storing first index of Preff sum in map 
     because since the elements are positive the preff sum will be increasing 
     and if before 'i'th element we have total/2 then for suffix sum also we have total/2 */
    for(int i=1;i<n;i++){
        preffSum[i]=nums[i]+preffSum[i-1];
        if(mpPref.find(preffSum[i])==mpPref.end())mpPref[preffSum[i]]=i;
    }
    suffSum[n-1]=nums[n-1];
    mpSuff[suffSum[0]]=0;
    /*
        Same reason for storing map of suffixes.
    */
    for(int i=n-2;i>=0;i--){
        suffSum[i]=nums[i]+suffSum[i+1];
        if(mpSuff.find(suffSum[i])==mpSuff.end())mpSuff[suffSum[i]]=i;
    }
    // 'i' in somewhere between (0,n-1) exclusive
    //[4,4,3,4,4,8] 4->4->4 & 4->8
    //[8,4,4,3,4,4] 8->4 & 4->4->4
    // 'i' 0 or N-1 
    //[3,4,4,4,8,4] 4->4->4 & 8->4 (i==0)
    //[4,4,4,8,4,3] 4->4->4 & 8->4 (i==n-1)
    for(int i=0;i<n;i++){
        int suff=suffSum[i+1];
        if(i==0) {
            if(suff%2!=0)continue;
            if(mpSuff.find(suff/2)!=mpSuff.end()&&mpSuff[suff/2]>0)return true;
            continue;
        }
        int preff=preffSum[i-1];
        if(i==n-1) {
            if(preff%2!=0)continue;
            if(mpPref.find(preff/2)!=mpPref.end()&&mpPref[preff/2]<n-1)return true;
            continue;
        }
        int total=preff+suff;
        if(total%2!=0)continue;
        if(preff==suff && preff==total/2 
        || preff<suff&&mpSuff.find(total/2)!=mpSuff.end()&&mpSuff[total/2]>i 
        || preff>suff&&mpPref.find(total/2)!=mpPref.end()&&mpPref[total/2]<i) return true;
    }
    return false;
}

int main(){
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--) {
        int n;
        cin>>n;
        vector<int> nums(n);
        for(int i=0;i<n;i++){
            int x;
            cin>>x;
            nums[i]=x;
        } 
        cout<<doesChainExists(nums)<<"\n";
    }
}


/* TestCases

5
6
4 4 3 4 4 8
6
8 4 4 3 4 4 
6
3 4 4 4 8 4
6
4 4 4 8 4 3
4
2 2 3 2

*/

/* output

1
1
1
1
0

*/