1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 struct node{ 5     ll num; 6     char ch; 7 }s[100010]; 8 ll p[110010],sum[110010],bit[110010]; 9 ll t,n,a,k,id,maxlen,tt;10 ll read(ll i){11     ll res=0;12     while(i){13         res+=bit[i];14         i-=i&-i;15     }16     return res;17 }18 void add1(ll i,ll x){19     while(i<110010){20         bit[i]+=x;21         i+=i&-i;22     }23 }24 int main(){25     scanf("%lld",&t);26     while(t--){27         memset(p,0,sizeof p);28         memset(bit,0,sizeof bit);29         memset(s,0,sizeof s);30         memset(sum,0,sizeof sum);31         scanf("%lld",&n);32         k=0;33         for(int i=0;i<n;i++){34             k++;35             //cin>>s[k].num>>s[k].ch;36             scanf("%lld %c",&s[k].num,&s[k].ch);37             tt=s[k].num;38             if(s[k].ch==s[k-1].ch){39                 s[k-1].num+=s[k].num;40                 k--;41             }42             add1(k,tt);43         }44         id=0,maxlen=0;45         s[0].ch=‘*‘,s[k+1].ch=‘#‘;46         for(int i=1;i<=k;i++){47             if(p[id]+id>i) p[i]=min(p[2*id-i],p[id]+id-i);48             else p[i]=1; 49             while(s[i-p[i]].ch==s[i+p[i]].ch&&s[i-p[i]].num==s[i+p[i]].num)++p[i];50             if(p[i]+i>p[id]+id) id=i;51             sum[i]=read(i+p[i]-1)-read(i-p[i]);            52             if(s[i-p[i]].ch==s[i+p[i]].ch) sum[i]+=2*min(s[i-p[i]].num,s[i+p[i]].num);53             maxlen=max(maxlen,sum[i]);54         }55         printf("%lld\n",maxlen);    56     }57     return 0;58 }