ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Regional School Programming Contest 2010

About     Problems     Submit solution     Judge status     Standings
Contest is over

J. Masterpieces of World Architecture

Time limit: 1.0 second
Memory limit: 64 MB
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.

Input

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 ≤ ain) separated with a space, where ai is the number told by the ith student.

Output

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.

Samples

inputoutput
4
4 1 2 3
2
3
1 1 1
3
Problem Author: Vladislav Isenbaev, prepared by Oleg Dolgorukov
Problem Source: Ural Regional School Programming Contest 2010
To submit the solution for this problem go to the Problem set: 1794. Masterpieces of World Architecture