e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

Dynamic Programming - Linear

Цвяхи

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

Вхідні дані

У першому рядку кількість цвяхів n (1n100). У наступному рядку записано n чисел - координати усіх цвяхів (невід'ємні цілі числа, які не перевищують 10000).

Вихідні дані

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

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