1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
| # include <bits/stdc++.h>
using namespace std; typedef long long int LL;
# define abs(x) ((x)>0?(x):-(x))
const int N = 2e6+10;
/******************************************************/
int z[N],f[N],p[N],n;
int sum[N*4]; # define lowbit(x) (x&-x) void update(int i,int v){for(;i<n*4;i+=lowbit(i)) sum[i]+=v;} int getsum(int i){int ans=0; for(;i;i-=lowbit(i)) ans+=sum[i]; return ans;}
int main(){ memset(sum,0,sizeof(sum)); scanf("%d",&n); LL tmp=0,tem=0;int ans = 0,dd=n; for(int i=1;i<=n;i++){ scanf("%d",&p[i]); tmp+=abs(p[i]-i); update(p[i]-i+n,1); }
tem=tmp; for(int i=2;i<=n;i++){ tem-=abs(p[n-i+2]-n); tem+=abs(p[n-i+2]-1);
update(p[n-i+2]-(n-i+2)+n,-1);
int t=getsum(dd); tem+=t; tem-=n-1-t;
dd++; update(p[n-i+2]-1+dd,1);
if(tem<tmp){ tmp=tem; ans=i-1; } }
printf("%lld %d\n",tmp,ans); return 0; }
|