In the speedbreaker question, why do we need to do: mn[i]=min(mn[i],mn[i-1]),mx[i]=max(mx[i],mx[i-1]);. I (mostly) get everything besides that. Thanks in advance!

Full submission by Zqr123456 on Div 2 contest:

include<bits/stdc++.h>

using namespace std; int T,n,a[200005],mn[200005],mx[200005],l,r; void solve(){ cin>>n; for(int i=0;i<=n;i++)mn[i]=n+1,mx[i]=0; for(int i=1;i<=n;i++)cin>>a[i],mn[a[i]]=min(mn[a[i]],i),mx[a[i]]=max(mx[a[i]],i); for(int i=1;i<=n;i++){ mn[i]=min(mn[i],mn[i-1]),mx[i]=max(mx[i],mx[i-1]); if(mx[i]-mn[i]>=i){cout<<"0\n";return;} } l=1,r=n; for(int i=1;i<=n;i++)l=max(l,i-a[i]+1),r=min(r,i+a[i]-1); cout<<r-l+1<<'\n'; } signed main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>T; while(T--)solve(); return 0; }

Also, I get why the first condition is necessary for there to be a solutions and I get why the second part of the code finds that good interval, but I'm having a little trouble piecing together the sufficiency of the two to guarantee the right answer. Perhaps this is also why I font understand why you have to do the operations on the mins and maxes too.