Algorithmic issue

I am trying to find a O (n) algorithm for this problem but unable to do so even after spending 3 - 4 hours. The brute force method times out (O (n^2)). I am confused as to how to do it ? Does the solution requires dynamic programming solution ?

http://acm.timus.ru/problem.aspx?space=1&num=1794

In short the problem is this:

There are some students sitting in circle and each one of them has its own choice as to when he wants to be asked a question from a teacher. The teacher will ask the questions in clockwise order only. For example:

5

3 3 1 5 5

This means that there are 5 students and :

1st student wants to go third
2nd student wants to go third
3rd student wants to go first
4th student wants to go fifth
5th student wants to go fifth.

The question is as to where should teacher start asking questions so that maximum number of students will get the turn as they want. For this particular example, the answer is 5 because

3 3 1 5 5

2 3 4 5 1

You can see that by starting at fifth student as 1st, 2 students (3 and 5) are getting the choices as they wanted. For t开发者_如何学Chis example the answer is 12th student :

12

5 1 2 3 6 3 8 4 10 3 12 7

because

5 1 2 3 6 3 8 4 10   3 12 7

2 3 4 5 6 7 8 9 10 11 12 1

four students get their choices fulfilled.

---

It's actually a rather simple problem. If student k wants to be the jth to present, then she will be satisfied iff the (k - j + 1)th (modulo n) is the first to present. This should lead you to a a simple O(n) algorithm.