记录编号	444659	评测结果	TATAAAAAAA
题目名称	[Codeforces 819B] B先生和PR移位	最终得分	80
用户昵称	cstdio	是否通过	未通过
代码语言	C++	运行时间	2.782 s
提交时间	2017-09-03 18:35:51	内存使用	4.13 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<set>
#include<cassert>
using namespace std;
typedef long long LL;
/*LL abs(LL a){
	return a>0?a:-a;
}*/
typedef multiset<int> ST;
const int SIZEN=1000010;
const LL INF=1e15;
int N;
int P[SIZEN]={0};
LL ans=INF,best=-1;
void update(LL now,LL k){
	if(now<ans){
		ans=now;
		best=k;
	}
}
ST S;LL posnum=0,nonposnum=0;
LL lazy;//at any time, item x in S is actually a+lazy
LL now=0;
void insert(LL x){//insert real value x
	now+=abs(x);
	if(x>0) posnum++;
	else nonposnum++;
	S.insert(x-lazy);
}
void erase(LL x){//erase real value x
	ST::iterator key=S.find(x-lazy);
	assert(key!=S.end());
	now-=abs(x);
	if(x>0) posnum--;
	else nonposnum--;
	S.erase(key);
}
void total_dec(void){
	now-=posnum;
	now+=nonposnum;
	lazy--;
	int m=S.count(-lazy);//count number of 0s
	posnum-=m;
	nonposnum+=m;
}
void work(void){
	//for an operation, everything -1
	LL lazy=0;
	for(int i=1;i<=N;i++) insert(P[i]-i);
	update(now,0);
	for(int i=1;i<=N-1;i++){
		int t=N+1-i;//P[t]-N change to P[t]-1
		erase(P[t]-N);
		total_dec();
		insert(P[t]-1);
		update(now,i);
	}
	cout<<ans<<" "<<best<<endl;
}
void read(void){
	scanf("%d",&N);
	for(int i=1;i<=N;i++) scanf("%d",&P[i]);
}
int main(){
	freopen("MrBB1.in","r",stdin);
	freopen("MrBB1.out","w",stdout);
	read();
	work();
	return 0;
}