Задача D. Гвоздики ≡

Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб

Условие

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

Формат входного файла

В первой строке входного файла записано число N — количество гвоздиков (2 ≤ N ≤ 100). В следующей строке записано N чисел  — координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10 000).

Формат выходного файла

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

Ограничения

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
5
4 10 0 12 2
 
6
0.024s 0.006s 15