贪心、前缀和

考虑如果有给定的起始城市怎么做最优：向 $a_i$ 最小的未被占领的城市走，一路占领。有多个 $a_i$ 最小的城市是无所谓的，占领它们的先后顺序随意。

于是可以根据等于 $x$ 的最左元素 $a_{l_x}$ 和最右元素 $a_{r_x}$ 得到区间 $[l_x,r_x]$，可以发现如果 $x < r_x - l_x + 1$ 则必定无解，因为占领整个区间至少要 $r_x - l_x +1$ 个步骤。

由于要先占领所有小于 $x$ 的值的位置，值 $x$ 对应的区间还应该包含所有小于 $x$ 的正整数 $y$ 对应的区间 $[l_y,r_y]$，设 $[al_x,ar_x]$ 为这个区间，这可以前缀和处理得到。如果存在 $ar_x - al_x +1 > x$ 的情况则无解，否则必定存在解。

然后我没活了。

英雄可不能临阵脱逃啊，继续想，应该要利用一些性质。

由于 $\forall x \in a,ar_x - al_x +1 \leq x$ 可知 $\forall x \in a,r_x - l_x +1 \leq x$，令 $v = x - (r_x - l_x +1)$，那么对于 $x$ 而言合法的出发位置应当在区间 $[\max(l_x - v,1),\min(r_x + v,n)]$ 中。

记 $w_x$ 为 $x$ 在序列中的出现次数，将区间 $[\max(l_x - v,1),\min(r_x + v,n)]$ 加上 $w_x$，所有区间加操作结束后被加了 $n$ 次的位置可以成为起始位置，前缀和维护。

为了方便处理将序列离散化。

时间复杂度 $O(n \log n)$。

#include<bits/stdc++.h>
using namespace std;
int n,ans,a[200'005],l[200'005],r[200'005],p[200'005],w[200'005],al[200'005],ar[200'005],sum[200'005];
void solution(){
    cin>>n,ans=0;
    for(int i=1;i<=n;i++) cin>>a[i];
    copy(a+1,a+n+1,p+1),sort(p+1,p+n+1);
    int cnt=unique(p+1,p+n+1)-p-1;
    for(int i=1;i<=n;i++) a[i]=lower_bound(p+1,p+cnt+1,a[i])-p;
    for(int i=1;i<=cnt;i++) l[i]=n,r[i]=1;
    for(int i=1;i<=n;i++){
        l[a[i]]=min(l[a[i]],i);
        r[a[i]]=max(r[a[i]],i);
    }
    for(int i=1;i<=cnt;i++){
        al[i]=l[i],ar[i]=r[i];
        if(i!=1){
            al[i]=min(al[i],al[i-1]);
            ar[i]=max(ar[i],ar[i-1]);
        }
        if(ar[i]-al[i]+1>p[i]) return cout<<0<<'\n',void();
    }
    for(int i=1;i<=cnt;i++) w[i]=0;
    for(int i=1;i<=n;i++) sum[i]=0,++w[a[i]];
    for(int i=1;i<=cnt;i++){
        int x=p[i]-(r[i]-l[i]+1);
        l[i]=max(l[i]-x,1);
        r[i]=min(r[i]+x,n);
        sum[l[i]]+=w[i],sum[r[i]+1]-=w[i];
    }
    for(int i=1;i<=n;i++){
        sum[i]+=sum[i-1];
        if(sum[i]==n) ++ans;
    }
    cout<<ans<<'\n';
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}