[HOJ] 324 - Birthday

#include<stdio.h>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int A[1000005],s[1000005],v[1000005];
struct P{
    int a,b;
}in;
queue<P> que;
vector<int> vec;
int main(){
    int n,i,x,y,tmp,ans=99999999,flag,c=1;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&A[i]);
    go:;
    vec.clear();
    while(que.size()) que.pop();
    for(i=1;i<=n;i++){
        if(A[i]>=i){
            if(A[i]-i<i+n-A[i]) s[i-1]=A[i]-i;
            else s[i-1]=(i+n-A[i])*-1;
        }
        else{
            if(i-A[i]<=A[i]+n-i) s[i-1]=(i-A[i])*-1;
            else s[i-1]=A[i]+n-i;
        }
    }
    sort(s,s+n);
    for(i=n-1;i>=0;i--)
        if(i==n-1 || s[i]!=s[i+1])
            vec.push_back(s[i]);
    for(i=0;i<vec.size();i++)
        que.push((P){vec[i],(vec[i]-vec[(i+1)%vec.size()]+n*3)%n});
    tmp=flag=0;
    if(min(abs(que.front().a),abs(que.back().a))<ans)
        ans=max(abs(que.front().a),abs(que.back().a));
    for(i=0;i<=n;i++){
        que.front().a++;
        que.back().a++;
        if(que.front().a>n/2){
            in=que.front();
            in.a-=n;
            x=que.front().a-que.front().b;
            que.pop();
            que.push(in);
            que.front().a=x;
        }
        if(max(abs(que.front().a),abs(que.back().a))<ans)
            ans=max(abs(que.front().a),abs(que.back().a));
    }
    for(i=1;i<=n;i++)
        v[i]=A[i];
    for(i=1;i<=n;i++)
        A[i]=v[n-i+1];
    if(c++==1) goto go;
    printf("%d\n",ans);
}