Problem C
HKIO
Languages
en
is
Garðar is trying to optimize his program in the game HKIO. The program is written in assembly and he has been looking into how often each command in the program is executed. To that end he has run the program numerous times on different inputs and has tallied how often each command was executed. But now he wants to determine which section of the program is run the most on average. In other words, he wants to determine what contiguous subsequence of commands has the highest average number of executions. Can you help him? Garðar is too busy solving more HKIO programming challenges to do this himself.
Input
The first line of the input contains one positive integer $n$ satisfying $1 \leq n \leq 10^5$. It is followed by a single line with $n$ integers $r_1, \dots , r_ n$ satisfying $0 \leq r_ i \leq 10^9$ which are separated by spaces.
Output
Print the indices of the endpoints of the contiguous subsequence with the highest average number of executions. If more than one such pair of endpoints exist, print any one of them. Do note that the first command is command number $0$.
| Sample Input 1 | Sample Output 1 |
|---|---|
7 1 0 0 2 2 2 0 |
3 5 |
