```
input:
1
2
3 4
```
```
output:
4
```
by I_will_AKIOI @ 2024-04-27 18:14:30
@[I_will_AKIOI](/user/565265) 啊?
by fish_love_cat @ 2024-04-27 18:15:56
@[fish_love_cat](/user/754021) 开始需要先用 $3$ 解锁啊,然后再拿 $4$。
by I_will_AKIOI @ 2024-04-27 18:17:28
@[I_will_AKIOI](/user/565265) 我的代码极度鬼畜(
还有吗qwq
by fish_love_cat @ 2024-04-27 18:47:41
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[100005],b[100005],f[100005],qzh[100005];
signed main(){
int t;
cin>>t;
b[0]=1;
while(t--){
cin>>n;
int cute=1145141919;
vector<int>v;
vector<int>w;
int k=0;
for(int i=1;i<=n;i++){
cin>>a[i];
qzh[i]=qzh[i-1]+a[i];
if(i+a[i]>n&&i<n){b[i]=b[i-1]-1;
if(i+a[i]-n<=cute)cute=i+a[i]-n,v.push_back(i),f[i]=-1;
else f[i]=a[i],a[i]=0;
}else if(a[i]<b[i-1])f[i]=a[i],b[i]=b[i-1]-1,a[i]=0;
else b[i]=a[i];
}
int f_f=1,ans=0,maxx[100005]={};
if(f[1]!=-1)maxx[0]=a[1];
for(int i=1;i<=min(f_f,n);i++){
int cat=-114514;
for(int j=i;j<=min(n,f_f);j++){
maxx[j]=maxx[j-1];
if(!f[j]){
cat=j;
maxx[j]=max(maxx[j],ans-a[cat]+qzh[min(n,f_f+a[cat])]);
}
if(k<v.size()&&j==v[k]){
w.push_back(i-1);
k++;
}
}
if(cat==-114514)break;
ans-=a[cat];
f_f=cat+a[cat];
i=cat;
//cout<<f_f<<' '<<ans<<' '<<maxx[i]<<endl;
}
/*
cout<<"a ";
for(int i=1;i<=n;i++)cout<<a[i]<<' ';
cout<<endl;
cout<<"b ";
for(int i=1;i<=n;i++)cout<<b[i]<<' ';
cout<<endl;
cout<<"f ";
for(int i=1;i<=n;i++)cout<<f[i]<<' ';
cout<<endl;
cout<<"qzh ";
for(int i=1;i<=n;i++)cout<<qzh[i]<<' ';
cout<<endl;
cout<<"maxx ";
for(int i=1;i<=n;i++)cout<<maxx[i]<<' ';
cout<<endl;
cout<<"v ";
for(int i=0;i<v.size();i++)cout<<v[i]<<' ';
cout<<endl;
cout<<"w ";
for(int i=0;i<w.size();i++)cout<<w[i]<<' ';
cout<<endl;
*/
int nsdd=maxx[min(n,f_f)];
for(int i=0;i<v.size();i++){
if(f_f<v[i])break;
nsdd=max(nsdd,maxx[v[i]]+qzh[n]-qzh[w[i]+a[w[i]]]-a[v[i]]);
}
cout<<nsdd<<endl;
}
return 0;
}
```
by fish_love_cat @ 2024-04-27 18:53:45