FASTSHOP - Christmas shopping

no tags 

Christmas Plans

Description

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.

Input

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

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.

Examples

Input Input Input
212
5959
11874874874874874874874874874874
Output Output Output
3
2
3


Added by:BYU Admin
Date:2015-11-05
Time limit:1s-15s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 MAWK BC NCSHARP COFFEE DART FORTH GOSU JS-MONKEY JULIA KTLN OCT PROLOG PYPY3 R RACKET SQLITE SWIFT UNLAMBDA