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

January 19,20. One-dimentional Dynamic Programming

Гвозди

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

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

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

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

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

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