[SNCPC2024] 商路
题目描述
一个圆周被 $K$ 个点等分，这些点按照顺时针编号为 $1, 2, \cdots, K$。其中点 $a_1, a_2, \cdots, a_n$ 分别建造有一座市场 $M_1, M_2, \cdots, M_n$。
一条从市场 $i$ 出发，目标是市场 $j$ 的商路是有向线段 $M_i M_j$ ($i \neq j$) 且必须满足以下条件：
- 市场 $j$ 必须是距离市场 $i$ 最远的市场（如果有多个距离相同的最远的市场,那么任意一个均可）。
- 商路线段 $M_i M_j$ 不能与其他商路线段在起点或者终点以外的地方相交或重合。
最多可以存在多少条商路？
输入输出格式
输入格式
第一行包含两个整数 $K, n$ ($3 \leq K \leq 10^9, 3\leq n \leq \min(K,10^5) $)，由空格隔开，表示有 $n$ 个市场分布在圆周的 $K$ 等分点上。
第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$ ($1\leq a_1 < a_2 < \cdots < a_{n-1} < a_n \leq K$)，为建有市场的点的编号。
输出格式
输出一个整数表示最多可以存在的商路的数量。
输入输出样例
输入样例 #1
10 5
1 2 5 6 8
输出样例 #1
2
输入样例 #2
3 3
1 2 3
输出样例 #2
3
说明
对于第一个样例，其中两种可能的答案如下图所示：
