题目描述

小明是一名热爱下国际象棋的中学生。最近, 他迷上了一种新的下棋方式: 在一维棋盘上摆放棋子。

小明拥有一块长度为 $n$ 的一维棋盘,棋盘上的位置从 $1$ 到 $n$ 编号。初始时, 棋盘上已经摆放了 $m$ 枚棋子, 剩余的位置都是空的。小明希望将棋盘上所有空位都摆满棋子, 以展现出优美的棋局。

为了达成这个目标,小明可以进行以下两种操作:

• 直接在任意一个空位上摆放一枚新棋子,该操作需要花费 $1$ 个金币。
• 利用已有棋子的位置关系来免费摆放新棋子。若存在两个已摆放棋子的位置 $i$ 和 $j$ $(i < j)$, 且它们的中点位置 $x$ 恰好是空位, 同时位置 $i$ 到位置 $j$ 之间 (不包括 $i, j$ 本身) 没有其他棋子, 则可以在位置 $x$ 免费摆放一枚新棋子。

小明想知道,要将棋盘上的所有空位都摆满棋子, 最少需要花费多少金币? 你能帮助他计算出这个最小花费吗?

输入格式

第一行输入两个非负整数 $n, m$。

第二行包括 $m$ 个正整数，表示哪些位置已经被摆放了棋子。

输出格式

一行一个整数，表示最少的代价。

样例数据

10 2
2 5

4

大样例

P1505.in /P1505.out

数据范围

对于 $20\%$ 的数据，$n \leq 8$。

对于 $40\%$ 的数据，$n \leq 20$。

对于 $60\%$ 的数据，$n \leq 10^3$。

对于 $80\%$ 的数据，$n \leq 10^6$。

对于 $100\%$ 的数据，$n \leq 10^{18}, 0 \leq m \leq 5$。

其中对于额外的 $30\%$ 的数据 $m = 0$ 。