Documentation
¶
Overview ¶
G. Бонусы для водителей Водители Яндекс.Такси узнали о раздаче бонусов и выстроились перед офисом. У каждого водителя есть рейтинг. Необходимо раздать водителям бонусы, соблюдая следующие условия: • Сумма бонуса кратна 500 рублям. • Каждый водитель должен получить как минимум 500 рублей. • Водитель с бóльшим рейтингом должен получить бóльшую сумму бонуса, чем его соседи слева или справа с меньшим рейтингом.
Какое минимальное количество денег потребуется на бонусы?
Формат ввода На первой строчке записано число N (1 <= N <= 20000), далее следует N строчек с рейтингами водителей Rn (0 <= Rn < 4096)
Формат вывода Ответ должен содержать минимально необходимое количество денег для выплаты вознаграждений
Пример 1 Ввод Вывод 4 5000 1 2 3 4
Пример 2 Ввод Вывод 4 2000 5 5 5 5
Пример 3 Ввод Вывод 4 3000 4 2 3 3
Source Files