不知道为什么错了，求hack

/*
   卫风·芄兰
芄兰之支,童子佩觿.
虽则佩觿,能不我知?
容兮遂兮,垂带悸兮.
芄兰之叶,童子佩韘.
虽则佩韘,能不我甲?
容兮遂兮,垂带悸兮.
*/
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define PII pair<int,int>
#define tul tuple<int,int,int>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define rep_(i,a,b) for(int i=a;i>=b;--i)
#define all(x) x.begin(),x.end()
#define bp(x) __builtin_popcountll(x)
#define cy cout<<"YES"<<endl
#define cn cout<<"NO"<<endl
#define lc (rt<<1)
#define rc (rt<<1|1)
mt19937_64 rnd(time(0));
const int N=2e6+5,yyx=1e9+7;
vector<int> to[N];
int n,m,a[N],pre[N],suf[N];
inline int mod(int x){
  return (x%yyx+yyx)%yyx;
}
inline int cmin(int &x,int y){
  return x>y?x=y,1:0;
}
inline int cmax(int &x,int y){
  return x<y?x=y,1:0;
}
int cal(int x){
    return x%n?x%n:n;
}
inline void solve(){
  cin>>n;
  int res=0;
  rep(i,1,n) cin>>a[i],res+=a[i],a[i+n]=a[i];
  res/=n;
  vector<int> st;
  rep(i,1,2*n){
    while(st.size()&&a[st.back()]<=res) st.pop_back();
    if(st.size()) pre[cal(i)]=cal(st.back());
    else pre[cal(i)]=2e14;
    st.push_back(i);
  }
  st.clear();
  rep_(i,2*n,1){
    while(st.size()&&a[st.back()]<=res) st.pop_back();
    if(st.size()) suf[cal(i)]=cal(st.back());
    else suf[cal(i)]=2e14;
    st.push_back(i);
  }
//   rep(i,1,n) cout<<pre[i]<<" ";cout<<endl;
//   rep(i,1,n) cout<<suf[i]<<" ";
  set<int> s;
  long long ans=0;
  rep(i,1,n) if(a[pre[i]]>res) s.insert(pre[i]);
  rep(i,1,n){
    if(a[i]>=res) continue;
    int j=pre[i],k=suf[i];
    if(a[k]==res&&s.size()) k=*s.begin();
    if(a[j]==res&&s.size()) j=*s.rbegin();
    int lst=n+i-j,nxt=k-i;
    while(a[i]<res){
        if(a[k]==res&&s.size()) k=*s.begin();
        if(a[j]==res&&s.size()) j=*s.rbegin();
        lst=n+i-j,nxt=k-i;
        //cout<<lst<<" "<<nxt<<" "<<i<<endl;
        if(lst<=nxt){
            int old=a[i];
            a[i]=min(a[i]+a[j]-res,res);
            ans+=(a[i]-old)*lst;
            a[j]-=(a[i]-old);
            if(a[j]==res&&s.count(j)) s.erase(j);
            //cout<<a[i]<<" "<<old<<endl;
        }
        else{
            int old=a[i];
            a[i]=min(a[i]+a[k]-res,res);
            ans+=(a[i]-old)*nxt;
            a[k]-=(a[i]-old);
            if(a[k]==res&&s.count(k)) s.erase(k);
        }
        //cout<<ans<<endl;
    }
  }
  cout<<ans<<endl;
}
signed main(){
  cin.tie(0)->sync_with_stdio(0);
  //freopen("D://321//in.txt","r",stdin);
  //freopen("D://321//out.txt","w",stdout);
  int _=1;
  //cin>>_;
  while(_--)
  solve();
  return 0;
}