Prison Release Cost Minimization

In the Caima Kingdom, there is a peculiar prison with \(P\) cells arranged in a line. Each cell is adjacent to its immediate neighbor. Initially, every cell is occupied by one prisoner. A release order is issued such that every day one prisoner from a given release list is freed. However, when a prisoner is released, all remaining prisoners in the contiguous group (i.e. those who can still communicate with the released cell) become angry and cause a commotion. To keep the peace, the guards must provide meat to calm them down. The cost for releasing a prisoner is equal to the number of prisoners (in that contiguous block) who become angry due to the release. After a release, the prison is effectively split into smaller contiguous blocks (separated by the empty cell).

Your task is to determine the minimum total amount of meat required to pacify the angry prisoners if the prisoners are released optimally according to the given release list.

Note: This problem is equivalent to the classic "Bribe the Prisoners" challenge, where dynamic programming over intervals is used to minimize the total cost (meat requirement).

inputFormat

The input consists of two lines.

The first line contains two space-separated integers: \(P\) (the total number of prison cells) and \(Q\) (the number of prisoners to be released).

The second line contains \(Q\) space-separated integers representing the cell numbers of the prisoners to be released. The positions may not be in sorted order; they are all distinct and lie between 1 and \(P\) (inclusive).

outputFormat

Output a single integer: the minimum total amount of meat required to pacify the angry prisoners when they are released in an optimal order.

sample

8 1
3

7