Competitions

# Dynamic Programming - Linear

# Nails

Some nails are hammered on a straight plank. Any two nails can be joined by a thread. Connect some pairs of nails with a thread, so that to each nail will be tied with at least one thread, and the total length of all threads will be minimal.

#### Input

The first line contains the number of nails **n** (**1** ≤ **n** ≤ **100**). The next line contains **n** numbers - the coordinates of all the nails (non-negative integers not exceeding **10000**).

#### Output

Print the minimum total length of all threads.

Input example #1

5 4 10 0 12 2

Output example #1

6