e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
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 (1n100). 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.

Time limit 1 second
Memory limit 128 MiB
Input example #1
5
4 10 0 12 2
Output example #1
6