Problem G
Herdier Immunity
You own a lovable pack of $N$ Herdiers that are numbered from $1$ to $N$, and every day you line them up in numerical order and count them off lovingly to show your affection to them. Unfortunately, tragedy struck one day, as $M$ of your Herdiers suddenly fell sick with some mysterious illness. Luckily, it wasn’t serious, but you still wanted to minimize the spread of this illness using the power of science.
Every day when your Herdiers are lined up, each already infected Herdier infects any uninfected adjacent Herdiers (two Herdiers numbered $i$ and $j$ are considered adjacent if $|i-j| = 1$). However, you obtain one vaccine every morning, and before lining them up each day you are able to vaccinate a single Herdier that isn’t infected already. After a Herdier is vaccinated, it cannot be infected, even in future days. You keep vaccinating Herdiers every day until all Herdiers either have the illness or are vaccinated. What is the maximum number of Herdiers you can vaccinate?
Input
The input starts with one line containing two space-separated integers $N$ and $M$. This denotes the total number of Herdiers ($1 \leq N \leq 10^9$) and the number of Herdiers that fell sick initially ($1 \leq M \leq 100\, 000$).
The second line contains $M$ distinct space-separated integers $a_1, \ldots , a_ M$ ($1 \leq a_1 < \ldots < a_ M \leq N$) where each $a_ i$ represents that the Herdier numbered $a_ i$ is initially infected.
Output
Output a single line containing the maximum number of Herdiers you can vaccinate.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 1 2 |
1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
12 2 4 9 |
5 |
| Sample Input 3 | Sample Output 3 |
|---|---|
23 3 4 12 20 |
8 |
