Bribing the Prisoners

Interview

Time limit2sMemory limit512 MB

Summary

Release Q prisoners from a row of P cells in the order that minimizes bribes paid to neighbors reached by the news. Find that minimum total cost.

Level: Medium7 of 10
Topics: Dynamic programming, Intervals, Divide and conquer
Solved: No attempts yet

Problem

A prison has $P$ cells in one row, numbered $1, 2, \dots, P$ from the left. Every cell is a solitary cell and holds exactly one prisoner. Neighboring cells share a window, so a prisoner can talk to the prisoner next door.

When you release the prisoner of some cell, the prisoner in each cell right next to it learns about it and starts a riot. Releasing one prisoner therefore costs one gold coin for the prisoner in each of the two neighboring cells. The news keeps traveling sideways from window to window, so you have to pay every prisoner the news reaches. An empty cell has no prisoner to pass the news along, so the news stops there.

Today you release the $Q$ prisoners held in cells $A_1, A_2, \dots, A_Q$ . The number of coins depends on the order of the releases. Find the order that spends the fewest coins and report how many coins that order needs.

Input

The first line contains two integers $P$ and $Q$ separated by a space. ( $1 \le P \le 10\,000$ , $1 \le Q \le 100$ , $Q \le P$ )

The second line contains $Q$ integers $A_1, A_2, \dots, A_Q$ separated by spaces. Each value is the cell number of a prisoner to release, and no value is given twice. ( $1 \le A_i \le P$ )

Output

Print on one line the minimum number of gold coins needed to release all $Q$ prisoners.

Examples2

Example 1
Input
```
8 1
3
```
Expected output
```
7
```
Example 2
Input
```
20 3
3 14 6
```
Expected output
```
35
```