Задача №112023. Оптимальное решение задач
Васин преподаватель по математике индивидуально подходит к оценке результатов своих учеников. Его интересует прежде всего прогресс. Ученикам предлагаются задачи в определенной последовательности, каждая имеет сложность от 1 до 5000. За решение ученик получает баллы, равные разнице сложности текущей задачи с предыдущей. За решение самой первой решенной задачи ученик получает баллы, равные ее сложности. Задачи можно решать только в порядке увеличения сложности.
Какие задачи стоит решить Васе, чтобы набрать максимально возможный результат по сумме баллов?
В первой строке дано одно число n ( 1 ≤ n ≤ 5000 ) — количество задач. Во второй строке даны сложности задач в том порядке в котором их можно решать. Если задача А идет в этом списке раньше задачи Б, то решать задачу А Вася должен раньше задачи Б.
Выведите последовательность, в которой Вася должен решать задачи (выведите последовательность сложностей задач). В случае, если есть несколько способов добиться получения максимального балла выведите любую оптимальную последовательность.
Пример входных данных
2 1 5 6 4
Пример выходных данных
1 6
Есть и другие варианты решения