Description

There is a strange prison in the Kingdom of Caima. The prison has $P$ cells arranged in a line, where the $i$-th cell is adjacent to the $(i+1)$-th cell (except for the last one). All cells are currently full.

A release list has been issued from above, requiring one person from the list to be released each day. This frightens the guards, because the $P$ prisoners can pass messages between adjacent cells. If someone leaves, then the people who could talk to this person will pass the news to everyone they can reach. Everyone who learns about it will become furious and will keep shouting that day, which gives the guards a headache. If you give meat to those who are about to get angry, they will calm down.

Input Format

The first line contains two integers $P$ and $Q$, where $Q$ is the number of people on the release list.

The second line contains $Q$ integers, indicating which prisoners to release, guaranteed to be given in increasing order.

Output Format

Output a single line with the minimum total number of person-times of meat deliveries.

20 3
3 6 14

35

Hint

Sample Explanation #1

First release the prisoner in cell $14$: you need to feed the $19$ people in cells $1$ to $13$ and $15$ to $20$. Then release the prisoner in cell $6$: you need to feed the $12$ people in cells $1$ to $5$ and $7$ to $13$. Finally, release the prisoner in cell $3$: you need to feed the $4$ people in cells $1$ to $2$ and $4$ to $5$.

Constraints

• For $50\%$ of the testdata, $1 \le P \le 100$, $1 \le Q \le 5$.
• For $100\%$ of the testdata, $1 \le P \le 10^3$, $1 \le Q \le 100$, $Q \le P$, and the indices of the prisoners to be released are given in increasing order.

Translated by ChatGPT 5