Задача Mountain. Для поповнення бюджету країни, що відома своїми гірськими маршрутами, ввели новий податок для альпіністів. Величина податку пропорційна довжині маршруту, але, оскільки маршрут проходить по горах і пройдену відстань, яка залежить від висоти спуску і підйому, підрахувати складно, податок утримується без урахування висоти, тобто величина податку пропорційна горизонтальному переміщенню туристичної групи. Крім того, в силу старовинного звичаю усі туристичні групи повинні переміщатися по горах строго із заходу на схід. Експедиція хоче заощадити на податку, тому вона розробляє гірський маршрут з мінімальною величиною податку. При цьому, оскільки маршрут є гірським, він повинен містити підйом в гору і спуск з гори, тобто на маршруті має бути точка, яка знаходиться строго вище початку і кінця маршруту.
Альпіністи склала карту, що містить інформацію про висоту гір при пересуванні із заходу на схід. Висоти гір виміряні в точках через рівні відстані. Знайдіть на цій карті туристичний маршрут, за який податок буде мінімальний, а підйом та спуск, як і личить альпіністам, буде на маршруті.
Технічні умови. Програма Mountain читає з пристрою стандартного введення число N - кількість точок на карті гір. У наступному рядку N чисел через пропуск містять інформацію про висоту гір в даних N точках при русі із заходу на схід. Всі числа натуральні, не перевищують 105. Програма виводить два числа - номер точки початку маршруту і номер точки закінчення маршруту. Точки нумеруються від 1 до N. Якщо маршруту, що задовольняє умовам, не існує, програма повинна вивести одне число 0. Якщо знайдеться декілька маршрутів, то вивести той що починається ближче до точки старту експедиції.
Приклади
Введення |
Виведення |
7 18 10 15 20 20 10 3 |
3 6 |
3 9 8 5 |
0 |
© LIKT 1998-2018