题目链接：

题目：

题解：

记旋转i次之后的答案为$ans_i$，分别考虑每个元素对ans数组的贡献

若$s_i<i$：

对$ans_0,..,ans_{i-s_i}$，贡献分别是$i-s_i,i-s_i-1,...,0$

对$ans_{i-s_i+1},...,ans_{i-1}$，贡献分别是$1,...,s_i-1$

对$ans_i,...,ans_{n-1}$，贡献分别是$n-s_i,...,i+1-s_i$

若$s_i=i$：

对$ans_0$，贡献是$0$

对$ans_1,...,ans_{i-1}$，贡献分别是$1,...,i-1$

对$ans_i,...,ans_{n-1}$，贡献分别是$n-i,...,1$

若$s_i>i$：

对$ans_0,...,ans_{i-1}$，贡献分别是$s_i-i,...,s_i-1$

对$ans_i,...,ans_{i+n-s_i}$，贡献分别是$n-s_i,...,0$

对$ans_{i+n-s_i+1},...,ans_{n-1}$，贡献分别是$1,...,s_i-i-1$

发现都是公差为$1$或$-1$的等差数列，显然线段树可以维护，但是数据范围不允许而且我们也不需要。怎么办呢？我们差分

对ans数组二阶差分即可，注意二阶差分的同时需要在一阶差分消去影响

注意差分的题目手动模拟是很有必要的，每个差分独立考虑

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;typedef long long ll;const int N=2e6+15;const ll inf=1e15;int n;ll s[N],cha1[3][N],cha2[3][N],a[N],b[N],p[N];inline int read(){    char ch=getchar();int s=0,f=1;    while (ch<'0'||ch>'9') {
   if (ch=='-') f=-1;ch=getchar();}    while (ch>='0'&&ch<='9') {s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}    return s*f;}int main(){    n=read();    for (int i=1;i<=n;i++) s[i]=read();    for (int i=1;i<=n;i++)    {        if (s[i]
         
          i)        {            if (0<=i-1) {cha1[2][0]++;cha1[2][i]--;cha1[1][0]+=s[i]-i-1;cha1[1][i]-=s[i]-1;}            if (i<=i+n-s[i]) {cha2[2][i+n-s[i]-1]++;cha2[2][i-1]--;cha2[1][i-1]-=n-s[i];}            if (i+n-s[i]+1<=n-1) {cha1[2][i+n-s[i]+1]++;cha1[2][n]--;cha1[1][n]-=s[i]-i-1;}        }    }    for (int i=0;i
          
           =0;i--) p[i]=p[i+1]+cha2[2][i]; for (int i=n-1;i>=0;i--) cha2[1][i]+=p[i]; for (int i=0;i
           
            =0;i--) b[i]=b[i+1]+cha2[1][i]; ll mi=inf; for (int i=0;i