|
Темы:
One-Dimensional Arrays
Dynamic programming
Using sort
Order statistics
Dynamic Programming: One Parameter
Anton B., a super bright 8th grade student, has unsurprising math skills. Having once been on an excursion in Kolokolamsk, he realized that he could easily write a program that would predict the cost of his favorite sweets for any period of days ahead.
Using this program, Anton B. decided to buy sweets with all his pocket money (and he had only 10 rubles of them), then, a little later, sell all the sweets he bought. Thus, Anton B. wants to earn as much money as possible for a new laptop.
Since Anton B. is still a minor and cannot go to other cities alone, he needs to figure out which of the two days to ask his older brother to take him to Kolokolamsk. The older brother is an adult and loves his younger brother very much, so he is always ready to help him.
Since Anton B. is in a hurry for the computer science class, he asks you to determine these two days in the next N days.
Input
The first line contains the number N (2 <= N <= 100000) the number of days for which Anton B. makes a forecast. The second line contains N positive integers ai (1 <= i <= N , 1 <= ai <= 5000 ) , where ai is the predicted cost of candies on the ith day.
Output
Print two numbers: the first number is the number of the day on which Anton B. will go to buy sweets, the second - the number of the day on which he will go to sell sweets. If there are several such variants of days, print any of them. If in the end Anton B. cannot make a profit under any of the options, print two zeros.
Examples
| # |
Input |
Output |
| 1 |
6
10 3 5 3 11 9
|
2 5
|
| 2 |
4
5 5 5 5
|
0 0
|
|