题目描述

一个圆周被 $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$)，为建有市场的点的编号。

输出格式

输出一个整数表示最多可以存在的商路的数量。

10 5
1 2 5 6 8

2

3 3
1 2 3

3

提示

对于第一个样例，其中两种可能的答案如下图所示：