|
Темы:
Одномерные массивы
Динамическое программирование
Использование сортировки
Порядковые статистики
Динамическое программирование: один параметр
Антон Б., суперспособный ученик 8 класса, обладает неудивительными математическими способностями. Побывав однажды на экскурсии в Колоколамске, он понял, что легко может написать программу, которая бы предсказывала стоимость его любимых конфет на любой промежуток дней вперед.
Используя эту программу, Антон Б. решил приобрести на все свои карманные деньги конфеты (а их у него было всего 10 рублей), затем, чуть позже, продать все купленные им конфеты. Таким образом, Антон Б. хочет заработать как можно больше денег на новый ноутбук.
Так как Антон Б. еще несовершеннолетний и один ездить в другие города не может, ему нужно понять, в какие из двух дней попросить старшего брата отвезти его в Колоколамск. Старший брат совершеннолетний и очень любит своего младшего брата, поэтому всегда готов ему помочь.
Так как Антон Б. очень торопится на кружок по информатике, он просит вас определить эти два дня в ближайшие N дней.
Входные данные
В первой строке записано число N (2 <= N <= 100000) количество дней, на которые Антон Б. делает прогноз. Вторая строка содержит N целых положительных чисел ai (1 <= i <= N , 1 <= ai <= 5000 ), где ai - предсказанная стоимость конфет в i-й день.
Выходные данные
Выведите два числа: первое число - номер дня, в который Антон Б. поедет покупать конфеты, второе - номер дня, в который он поедет продавать конфеты. В случае, если таких вариантов дней несколько, выведите любой из них. Если Антон Б. в итоге не сможет получить прибыль ни при каких вариантах, то выведите два нуля.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
6
10 3 5 3 11 9
|
2 5
|
| 2 |
4
5 5 5 5
|
0 0
|
|