e-olymp
Соревнования

January 19,20. One-dimentional Dynamic Programming

Гвозди

На прямой дощечке вбиты гвоздики. Любые два гвоздика можно соединить ниточкой. Требуется соединить некоторые пары гвоздиков ниточками так, чтобы к каждому гвоздику была привязана хотя бы одна ниточка, а суммарная длина всех ниточек была минимальна.

Входные данные

В первой строке записано количество гвоздиков n (1n100). В следующей строке записано n чисел - координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10000).

Выходные данные

Вывести минимальную суммарную длину всех ниточек.

Лимит времени 1 секунда
Лимит использования памяти 122.17 MiB
Входные данные #1
5
4 10 0 12 2
Выходные данные #1
6