thanks, I understand

I also had WA#3, but this test is AC. My solution used BFS. Please, help me! Thanks!

#pragma comment(linker,"/STACK:8000000")
#include <stdio.h>

int loading(int &N,int** (&M)){
    int *Left,*Right;
    scanf("%d",&N);
    if(N==0) {printf("%d",0); return -1;}
    Left=new int[N]; Right=new int[N];
    int tmpL,tmpR;
    for(int i=0;i<N;++i) {scanf("%d %d",&tmpL,&tmpR); /*if(tmpR<tmpL) {int tmp=tmpR; tmpR=tmpL; tmpL=tmp;}*/ Left[i]=tmpL; Right[i]=tmpR;}

    M=new int*[N];
    for(int i=0;i<N;++i) {M[i]=new int[N]; for(int j=0;j<N;++j) M[i][j]=0;}

    //i-ый отрезок вложен в j-ый
    for(int i=0;i<N;++i) for(int j=0;j<N;++j) if(Left[j]<Left[i] && Right[i]<Right[j]) {M[i][j]=1; M[j][i]=-1;}

    delete[] Left;delete[] Right;
    return 0;
}


int doing(int &N,int **(&M),int *(&Last),int &posBiggestWeight,int &BiggestWeight){
    Last=new int[N];
    int *Weight=new int[N];
    for(int i=0;i<N;++i) {Last[i]=-1; Weight[i]=0;}

    //Поиск отрезков, которые ни во что не вложены
    int *Roots=new int[N],iCountRoots=0;
    for(int i=0;i<N;++i){
        bool isNotRoot=true;
        for(int j=0;j<N && isNotRoot;++j) if(M[i][j]==1) isNotRoot=false;
        if(!isNotRoot){
            Roots[iCountRoots++]=i;
        }
    }

    //Перебор всех вложеных
    for(int k=0;k<iCountRoots;++k){
        int NeedVisit[1000000],cntNVisit=0;
        NeedVisit[cntNVisit++]=Roots[k]; Weight[Roots[k]]=0;
        while(cntNVisit>0){
            int tekVertex=NeedVisit[--cntNVisit],tekWeight=Weight[tekVertex],newWeight=tekWeight+1;
            for(int j=0;j<N;++j) if(M[tekVertex][j]==1 && newWeight>=Weight[j]){
                NeedVisit[cntNVisit++]=j; Weight[j]=newWeight; Last[j]=tekVertex;
            }
        }
    }
    //поиск максимального веса
    BiggestWeight=-2; posBiggestWeight=-1;
    for(int i=0;i<N;++i) if(Weight[i]>BiggestWeight){
        posBiggestWeight=i; BiggestWeight=Weight[i];
    }
    delete[] Weight;
    return 0;
}

int saveing(int &N,int* (&Last),int &posBiggestWeight,int &BiggestWeight){
    int *Answer=new int[BiggestWeight+1],pos=posBiggestWeight;
    int indAnswer=BiggestWeight;
    while(pos!=-1){
        Answer[indAnswer--]=pos+1; pos=Last[pos];
    }
    printf("%d\n",BiggestWeight+1);
    for(int i=0;i<BiggestWeight;++i) printf("%d ",Answer[i]); printf("%d\n",Answer[BiggestWeight]);
    delete[] Answer;
    return 0;
}

int main(){
    int N,**M,*Last,posBiggestWeight=0,BiggestWeight=0;
    int res=loading(N,M);
    if(res==-1) return 0;
    doing(N,M,Last,posBiggestWeight,BiggestWeight);
    saveing(N,Last,posBiggestWeight,BiggestWeight);

    delete[] Last;
    for(int i=0;i<N;++i) delete[] M[i];
    delete[] M;

    return 0;
}

My solution:
Calc b[i] - count of numbers such (n+A[i]-i)%n == i
Then find max_idx - index of maximum element in array b
answer is  (n - max_idx) % n + 1

did you get AC?
I don't think to satisfy most students is right. for example(the one you mentioned):
5
3 3 1 5 5
your answer is 5,so the sequence is 2 3 4 5 1. we can calculate the difference:
|3-2|+|3-3|+|1-4|+|5-5|+|5-1|=8
but for another sequence:1 2 3 4 5,the difference is:
|3-1|+|3-2|+|1-3|+|5-4|+|5-5|=6, is smaller than 8.
so as my conclusion, we should make the "displeasure" minimal. if using your method,
maybe a lot of students is "satisfied(the difference of him is 0)", but others maybe larger.
sorry for my bad English.

did you get AC?
I don't think to satisfy most students is right. for example(the one you mentioned):
5
3 3 1 5 5
your answer is 5,so the sequence is 2 3 4 5 1. we can calculate the difference:
|3-2|+|3-3|+|1-4|+|5-5|+|5-1|=8
but for another sequence:1 2 3 4 5,the difference is:
|3-1|+|3-2|+|1-3|+|5-4|+|5-5|=6, is smaller than 8.
so as my conclusion, we should make the "displeasure" minimal. if using your method,
maybe a lot of students is "satisfied(the difference of him is 0)", but others maybe larger.
sorry for my bad English.

i'd rather like this.  cuz it's clear :)