题目描述

向晚正在接受嘉然的考验。

首先，嘉然选出 $n$ 名嘉心糖排成一个序列 $a$ ，并依次编号为 $1,2,\cdots,n$ 。

接着，嘉然对嘉心糖们发布了 $m$ 条指令。每条指令都可以用一个整数 $x$ （ $1\le x < n$ ）描述，表示让当前处于 $x$ 号位置和 $(x+1)$ 号位置的嘉心糖贴贴并交换。

例如，对排列 $[5,1,4,2,3]$ 发布 $x=3$ 的指令，会将其变为 $[5,1,2,4,3]$ 。

最后，嘉然希望向晚能够找到一个尽可能大的嘉心糖集合 $S$ （ $S\subseteq \{1,2,\cdots,n\}$ ），使得集合内任意两个嘉心糖都曾经贴贴过。

输入格式

第一行两个整数 $n,m$ ，分别表示排列 $a$ 的长度和操作的数量。

接下来 $m$ 行，第 $i$ 行包含整数 $x_i$ ，表示第 $i$ 次操作的参数。

输出格式

输出一行共一个整数，表示集合 $S$ 大小的最大值。

数据范围

对于 $100\%$ 的数据， $2 \le n \le 2 \times 10^5$ ， $1 \le m \le 2 \times 10^5$ ， $1 \le x_i \le n-1$ 。

各子任务的具体信息见下表：

输入样例 1

6 6
1
1
4
5
1
4

输出样例 1

3

样例解释

交换过位置的元素对为 $(1,2)$ ， $(4,5)$ ， $(5,6)$ 和 $(4,6)$ 。

当 $S=\{4,5,6\}$ 时，集合 $S$ 的大小取到最大值 $3$ 。