FASTSHOP - Christmas shopping
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.
- Since the mall could close at any time, choose the way to get the most presents within one minute.
- If there is a tie, choose the way to get the most presents within two minutes.
- If there is a tie, choose the way to get the most presents within three minutes.
- And so on.
For example, suppose these are the stores in clockwise order:
Therefore, it is best to start at store 3.
- Store 1: two presents
- Store 2: one present
- Store 3: two 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.)
(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 |