Lack of planning (and arguing with stubborn physicists) has made you terribly behind on Christmas shopping. The mall is about to close, and you need to buy presents from several stores in the fastest time possible. The stores in the mall are arranged in a loop. You plan to visit each store sequentially in clockwise order, until you are done or the mall closes. It takes one minute to get necessary presents from each store.

Find the best store to start at.

1. Since the mall could close at any time, choose the way to get the most presents within one minute.
2. If there is a tie, choose the way to get the most presents within two minutes.
3. If there is a tie, choose the way to get the most presents within three minutes.
4. And so on.

For example, suppose these are the stores in clockwise order:

• Store 1: two presents
• Store 2: one present
• Store 3: two presents

Starting at store 1 or store 3 gives you the most number of presents in one minute (two presents). Starting at store 3 gives you the most presents in two minutes (four presents).
Therefore, it is best to start at store 3.

There are N (1 <= N <= 200,000) consecutive numerals 1-9, which are the number of presents at each of the N stores in clockwise order, starting with store 1 and ending with store N.
(Remember that the stores are in a loop, so store N is also next to store 1.)

Output the best store to start at, according to the criteria stated earlier. If multiple stores are best, choose the store with the lowest number.