Maria Ivanovna informed all of her fifth-graders that in a month they would have a class on the topic “Masterpieces
of World Architecture.” Each of the students had to prepare a short report about a famous architectural structure.
As always, the best students prepared their reports in advance and the worst students started preparing for the
class only several minutes before it.
The class has begun. According to the tradition, at such classes the children are sitting in a circle and speaking
one after another in clockwise order. The best students like to be the first to speak, while the worst students
want to be the last because they are trying to finish their reports right during the class.
Maria Ivanovna has asked each student which in turn they want to present their reports. Now she has to decide who
will be the first to speak so that as many children as possible will have their turn to speak exactly as they want.
The first line contains the number n of students in the class (2 ≤ n ≤ 105).
Maria Ivanovna has numbered all the children from 1 to n clockwise in the order in
which they are sitting. The second line contains integers a1, …, an (1 ≤ ai ≤ n)
separated with a space, where ai is the number told by the ith student.
Output the number of the student who should start the class “Masterpieces of World Architecture” by presenting
their report. If there are several possible answers, output any of them.
4 1 2 3
1 1 1
Problem Author: Vladislav Isenbaev, prepared by Oleg Dolgorukov
Problem Source: Ural Regional School Programming Contest 2010