记录编号	449134	评测结果	AAAAAAAAAA
题目名称	[Codeforces 819B] B先生和PR移位	最终得分	100
用户昵称	烟雨	是否通过	通过
代码语言	C++	运行时间	0.471 s
提交时间	2017-09-13 20:06:22	内存使用	76.61 MiB

#include<fstream>
#include<algorithm>
#include<cmath>
using namespace std;
ifstream cin("MrBB1.in");
ofstream cout("MrBB1.out");
long long f[5000002],n,q,l,r,ans=0,k=0,s[5000001];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s[i];
		ans=ans+abs(s[i]-i);
		if(s[i]>=i)
	    {
			l++;
			f[s[i]-i]++;
		}
		else 
		{
			r++;
		}
		/*cin>>q;
		s[i]=q;
		if(q>i)
		{
			f[q-i]++;
			l++;
			ans=ans+q-i;
		}
		if(q==i)
		{
			f[0]++;
		}
		if(q<i)
		{
			f[n-i+q]++;
			r++;
			ans=ans+i-q;
		}*/
	}
	//for(int i=1;i<=n;i++)cout<<s[i]<<endl;
	q=ans;
	for(int i=1;i<n;i++)
	{
		l=l-f[i-1];
		r=r+f[i-1];
		q=q+r-l-abs(s[n-i+1]-n-1)+abs(s[n-i+1]-1);
		if(q<ans)
		{
			ans=q;
			k=i;
		}
		f[s[n-i+1]+i-1]++;
		l++;
		r--;
		//cout<<l<<' '<<r<<' '<<q<<endl;
	}
	cout<<ans<<' '<<k;
	cin.close();
	cout.close();
	return 0;
}