#include <bits/stdc++.h>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3SJjfN1 ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e
struct fenwick{
int n;
vector <int> bit;
fenwick(int m){
init(m);
}
void init(int m){
n=m;
bit.resize(n+1,0);
}
int get(int i){
int s=0;
while(i<=n){
s+=bit[i];
i+=i&-i;
}
return s;
}
void add(int i,int x){
while(i>0){
bit[i]+=x;
i-=i&-i;
}
}
};
signed main(){
_3SJjfN1;
int n;
// n=100000;
cin>>n;
vi a(n);
rep(i,n){
// a[i]=randint((int)(1ll<<29))+1;
cin>>a[i];
}
// to the left i need
// x - pvt = y - i
// to the right i need
// x - y = i - pvt
// x + pvt = i + y
vi tmp;
rep(i,n){
tmp.pb(a[i]-i);
tmp.pb(a[i]+i);
}
sort(tmp.begin(),tmp.end());
tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
const int m=sz(tmp);
vi idsl(n),idsr(n);
rep(i,n){
int v=a[i]-i;
int j=lower_bound(tmp.begin(),tmp.end(),v)-tmp.begin();
idsl[i]=j;
int v=a[i]+i;
int j=lower_bound(tmp.begin(),tmp.end(),v)-tmp.begin();
idsr[i]=j;
}
// atcoder::segtree<int,op,e> segl(m),cntl(m),segr(m),cntr(m);
fenwick bitl(m),cntl(m),bitr(m),cntr(m);
int psunl=0,pcntl=0,psunr=0,pcntr=0;
auto af=[&](const int&pvt,const int&x)->int{
int res=0;
// to the left
int v=x-pvt;
// >=
int j=lower_bound(tmp.begin(),tmp.end(),v)-tmp.begin();
int sun=psunl,now=pcntl;
if(j>=0 and j<sz(tmp)){
int vala=bitl.get(j+1);
int valb=cntl.get(j+1);
res+=vala-valb*v;
sun-=vala;
now-=valb;
}
// <=
if(j>=0 and j<=sz(tmp)){
res+=now*v-sun;
}
// to the right
v=x+pvt;
j=lower_bound(tmp.begin(),tmp.end(),v)-tmp.begin();
sun=psunr,now=pcntr;
if(j>=0 and j<sz(tmp)){
int vala=bitr.get(j+1);
int valb=cntr.get(j+1);
res+=vala-valb*v;
sun-=vala;
now-=valb;
}
// <=
if(j>=0 and j<=sz(tmp)){
res+=now*v-sun;
}
return res;
};
rep(i,n){
int v=a[i]+i;
int j=idsr[i];
psunr+=v;
pcntr+=1;
bitr.add(j+1,v);
cntr.add(j+1,1);
}
const int inf=1e18;
int ans=inf;
rep(i,n){
int l=max(i+1,n-i),r=1e9;
while(r-l>2){
int ml=(2*l+r)/3;
int mr=(l+2*r)/3;
if(af(i,ml)<af(i,mr)){
r=mr;
}else{
l=ml;
}
}
rng(j,l,r+1){
ans=min(ans,af(i,j));
}
int v=a[i]+i;
int j=idsr[i];
psunr-=v;
pcntr-=1;
bitr.add(j+1,-v);
cntr.add(j+1,-1);
v=a[i]-i;
j=idsl[i];
psunl+=v;
pcntl+=1;
bitl.add(j+1,+v);
cntl.add(j+1,+1);
}
print(ans);
}
Compilation message
krov.cpp: In function 'int main()':
krov.cpp:77:8: error: redeclaration of 'll v'
77 | int v=a[i]+i;
| ^
krov.cpp:74:8: note: 'll v' previously declared here
74 | int v=a[i]-i;
| ^
krov.cpp:78:8: error: redeclaration of 'll j'
78 | int j=lower_bound(tmp.begin(),tmp.end(),v)-tmp.begin();
| ^
krov.cpp:75:8: note: 'll j' previously declared here
75 | int j=lower_bound(tmp.begin(),tmp.end(),v)-tmp.begin();
| ^
