题目
Some time ago Mister B detected a strange signal from the space, which he started to study.
After some transformation the signal turned out to be a permutation p of length n or its cyclic shift. For the further investigation Mister B need some basis, that's why he decided to choose cyclic shift of this permutation which has the minimum possible deviation.
Let's define the deviation of a permutation p as .
Find a cyclic shift of permutation p with minimum possible deviation. If there are multiple solutions, print any of them.
Let's denote id k (0 ≤ k < n) of a cyclic shift of permutation p as the number of right shifts needed to reach this shift, for example:
k = 0: shift p 1, p 2, ... p n, k = 1: shift p n, p 1, ... p n - 1, ..., k = n - 1: shift p 2, p 3, ... p n, p 1.
Input
First line contains single integer n (2 ≤ n ≤ 106) — the length of the permutation.
The second line contains n space-separated integers p 1, p 2, ..., p n (1 ≤ p i ≤ n) — the elements of the permutation. It is guaranteed that all elements are distinct.
Output
Print two integers: the minimum deviation of cyclic shifts of permutation p and the id of such shift. If there are multiple solutions, print any of them.
Examples
Input
3
1 2 3
Output
0 0
Input
3
2 3 1
Output
0 1
Input
3
3 2 1
Output
2 1
Note
In the first sample test the given permutation p is the identity permutation, that's why its deviation equals to 0, the shift id equals to 0 as well.
In the second sample test the deviation of p equals to 4, the deviation of the 1-st cyclic shift (1, 2, 3) equals to 0, the deviation of the 2-nd cyclic shift (3, 1, 2) equals to 4, the optimal is the 1-st cyclic shift.
In the third sample test the deviation of p equals to 4, the deviation of the 1-st cyclic shift (1, 3, 2) equals to 2, the deviation of the 2-nd cyclic shift (2, 1, 3) also equals to 2, so the optimal are both 1-st and 2-nd cyclic shifts.
题意
定义一个全排列 pi 的偏移值为∑ni=1| pi - i | 给你一个全排列，你可以从后面拿k∈[0,n−1]个数放在前面，使得该全排列的偏移值最小，输出这个偏移值和k，如果有多个k任意输出一个
分析
我们当前位的数的本身的大小是不变的，而我们每操作一次它的编号 i 就会增大1 。
那么，对于这次操作偏移值为正数的，结果的总贡献就回少1，也就是ans一共会减少原偏移值为正的数的个数。
对于此次操作偏移值为非正的，显然对ans的贡献会加1，所以ans的增加量是原偏移值为非正数的数的个数。
所以，我们要找的就是原偏移值为正的和非正的数的个数。
然后我们就可以考虑了，经过一次操作，原偏移值为+1的数偏移值都会变为0，所以，原偏移值为正数的数的个数会少掉原偏移值为+1的数的个数。
而原偏移值为非正数的数的个数会加上原偏移值为+1的数的个数，这也是显然的。所以原偏移值为非正的数的个数不会变少，只会越来越多。
最后每次我们把第 n-i+1 位的数放到最前面，然后他的改变就直接算就行。
代码
#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define ll long long using namespace std; const int maxn=3e6+10; int a[maxn]; ll ans,k; ll cnt,sum; ll one[maxn]; int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); int x=a[i]-i; if(x<=0){ sum++; ans+=abs(x); } else{ cnt++; ans+=x; one[x]++; } } ll tmp,tmpp=ans; if(ans==0){ printf("0 0 "); return 0; } for(int i=1;i<n;i++){ tmp=tmpp; tmp-=cnt; tmp+=sum; cnt-=one[i]; sum+=one[i]; ll x=a[n-i+1]; tmp-=n+1-x; sum--; if(x>1){ one[x-1+i]++; tmp+=x-1; cnt++; } else sum++; if(tmp<ans){ ans=tmp; k=i; } if(ans==0){ printf("%d %d ",ans,k); return 0; } tmpp=tmp; } printf("%d %d ",ans,k); return 0; }