Here is my code:

#include <iostream>

using namespace std;

//long int _wants[200002];
//long int _nums[100001];
long int n;

long int *_wants;
long int *_nums;

int main()
{
   cin>>n;
   _wants = new long int[2*n];
   _nums = new long int[n];

   for (long int i=0; i<n; i++) cin>>_wants[i];

   for (long int i=0; i<n; i++)
   {
      _nums[i]=_wants[i];
      _wants[i]-=i+1;
      _wants[i+n]=_wants[i]-n;
   }

   long int _max=_wants[0];
   long int _pos=1;
   long int _count=1;
   for (long int j=0; j<n; j++)
   {
      if (_wants[j]>-n)
      {
         _count=1;
         for (long int i=j+1; i<2*n; i++)
         {
            if (_wants[i]==_wants[j])
            {
               _wants[i]=-n;
               _count++;
            }
         }
         _wants[j]=_count;
         if (j==0) _max=_wants[j];
         else if (_wants[j]>_max)
         {
            _max=_wants[j];
            _pos=j-(_nums[j])+2;
         }
      }
   }

   if (_pos<=0) _pos+=n;

   cout<<_pos<<endl;
   return 0;
}

My algo is following: we take the input twice, like this: for "4 1 2 3" - "4 1 2 3 4 1 2 3". For each standing in array of meanings we count arr[i]-i . For students standing in a right way to answer counting gives same results. Then we count a number of each difference in our array of 2*n elements, but only for meanings in left half of arr (and write it to the beginning of the arr). After that we will have the length of the longest sequence and its beginning position. There's no problem to say who must be first.

I found out that for n=99999 there's a TL. But why? This algo is enough fast...

Edited by author 25.10.2010 13:15

your program do O(n^2) operation (you have two embedded loop)