Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Mountain

Задача Mountain. Для поповнення бюджету  країни, що відома   своїми гірськими  маршрутами, ввели новий податок для альпіністів. Величина податку пропорційна довжині маршруту, але, оскільки маршрут проходить по горах і пройдену відстань, яка залежить від висоти спуску і підйому, підрахувати складно, податок утримується без урахування висоти, тобто величина податку пропорційна горизонтальному переміщенню туристичної групи. Крім того, в силу старовинного звичаю усі туристичні групи повинні переміщатися по горах  строго із заходу на схід. Експедиція хоче заощадити на податку, тому вона  розробляє гірський маршрут з мінімальною величиною податку. При цьому, оскільки маршрут є гірським, він повинен містити підйом в гору і спуск з гори, тобто на маршруті має бути точка, яка знаходиться строго вище початку і кінця маршруту.

Альпіністи склала карту, що містить інформацію про висоту гір при пересуванні із заходу на схід. Висоти гір виміряні в точках через рівні відстані. Знайдіть на цій карті туристичний маршрут, за який податок буде мінімальний, а підйом та спуск, як і личить альпіністам, буде на маршруті.

Технічні умови. Програма Mountain читає з пристрою стандартного введення  число N - кількість точок на карті гір. У наступному рядку N чисел через пропуск містять інформацію про висоту гір в даних N точках при русі із заходу на схід. Всі числа натуральні, не перевищують 105. Програма виводить два числа - номер точки початку маршруту і номер точки закінчення маршруту. Точки нумеруються від 1 до N. Якщо маршруту, що задовольняє умовам, не існує, програма повинна вивести одне число 0. Якщо знайдеться декілька маршрутів, то вивести той що починається ближче до точки старту експедиції.

Приклади

Введення

Виведення

7

18 10 15 20 20 10 3

3 6

3

9 8 5

0


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"