Cutting a String

Cutting a string of length N into two pieces costs N.

Given the positions where a string must be cut, write a program that finds the minimum total cost of making every cut.

For example, suppose the string must be cut right after characters 3, 8 and 10, where the first character is number 1. If the string is thisisastringofchars, marking the cut positions with | gives thi|sisas|tr|ingofchars.

Cutting from the left in order costs 49.

thisisastringofchars     (string)
thi sisastringofchars    (cost 20)
thi sisas tringofchars   (cost 17)
thi sisas tr ingofchars  (cost 12)
                         total 49

Cutting from the right in order costs 38.

thisisastringofchars     (string)
thisisastr ingofchars    (cost 20)
thisisas tr ingofchars   (cost 10)
thi sisas tr ingofchars  (cost 8)
                         total 38

You choose the order of the cuts. Find the minimum total cost of making all of the given cuts.

The first line contains the length of the string N ($2 \le N \le 10^7$) and the number of cut positions M ($1 \le M \le 1000$, $M < N$), separated by a space.

The second line contains the M cut positions, separated by spaces, in increasing order. Each position is a distinct integer between $1$ and $N-1$, and it means the string is cut immediately after the character with that number.

Print the minimum total cost of making all of the given cuts on the first line.