1. Гвоздики

  • легкая
  • dynamic programming 1D

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

Формат ввода

В первой строке входных данных записано целое число $N$ ($2 \le N \le 100$) — количество гвоздиков.

В следующей строке задано $N$ попарно различных целых чисел $a_i$ ($0 \le a_i \le 10^4$) — координаты гвоздиков.

Формат вывода

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

Пример 1

Ввод
6
3 13 12 4 14 6
Вывод
5