B. Mister B
and PR Shifts
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
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 p1, p2, ... pn,
k =
1: shift pn, p1, ... pn -
1,
...,
k = n -
1: shift p2, p3, ... pn, p1.
Input
First line
contains single
integer n (
2 ≤ n ≤
106) —
the length of the permutation.
The
second line
contains n
space-separated integers p1, p2, ..., pn (
1 ≤
pi ≤ 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.
将p分为A:p[i]−i<=0 和 B:p[i]−i>0这2种
当p右移时,显然A的偏移量+1,B的偏移量−1
而最后一个p比较特殊,需要移动到最左边
因为p[n]−n<=0恒成立,恒属于A,而p[n]需要移动到pos=1,则p[1...n−1]的改变量为(A−1)−B
若∑ni=1(pi−i)=res,p右移后:res=res+(A−1)−B+(p[n]−n)+(p[n]−1)
于是问题转化为,如果高效维护A和B:
显然p[i]−i>0时,经过p[i]−i次右移,p[i]的偏移量会变成<=0
p[i]−i<=0时,经过p[i]−i+n次右移,p[i]偏移量先变为>0再变为<=0
记c[i]=∑ni=1[(p[i]−i+n)%n],第i次右移时,p[1...n−1]处,A会增加c[i]
则每次移动,A=A−1+c[i]
B=n−A
#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<list>
#define ll long long
#define pii pair<int,int>
#define MEM(a,x) memset(a,x,sizeof(a))
#define lowbit(x) ((x)&-(x))
using namespace std;
const int inf=
0x3f3f3f3f;
const int N =
1e6+
5;
int n,p[
2*N],c[N];
void slove(){
MEM(c,
0);
int a=
0,b=
0,resIdx=
0;
ll res=
0;
for(
int i=
1;i<=n;++i){
int idx=(p[i]-i+n)%n;
++c[idx];
res+=
abs(p[i]-i);
a+=p[i]<=i;
b+=p[i]>i;
}
ll tRes=res;
for(
int i=
1;i<n;++i){
int x=p[
2*n-i+
1];
tRes=tRes+(a-
1)-b-(n-x)+(x-
1);
a=a-
1+c[i];
b=n-a;
if(res>tRes){
res=tRes;
resIdx=i;
}
}
printf(
"%I64d %d\n",res,resIdx);
}
int main()
{
while(~
scanf(
"%d",&n)){
for(
int i=
1;i<=n;++i){
scanf(
"%d",&p[i]);
p[n+i]=p[i];
}
slove();
}
return 0;
}
