[Poi2011]Strongbox

密码箱的旋钮共有 $n$ 个位置，编号为 $0$ 到 $n-1$。其中一些位置可以打开密码箱，并满足如下性质：如果位置 $a$ 和 $b$ 都能打开密码箱，那么位置 $(a+b)\bmod n$ 也能打开密码箱，其中 $a$ 与 $b$ 可以相等。

Byteasar 依次尝试了 $k$ 个互不相同的位置 $m_1,m_2,\ldots,m_k$。前 $k-1$ 次尝试均未能打开密码箱，只有最后尝试的位置 $m_k$ 成功打开了密码箱。

在所有与这些尝试结果相符的密码箱中，请求出能够打开密码箱的位置数量的最大值。

输入格式

第一行包含两个整数 $n$ 和 $k$，分别表示旋钮位置的总数和尝试次数。

第二行包含 $k$ 个互不相同的整数 $m_1,m_2,\ldots,m_k$，依次表示每次尝试的位置。

保证输入数据对应至少一种满足题目条件的密码箱。

输出格式

输出一个整数，表示能够打开密码箱的位置数量的最大值。

样例输入

42 5
28 31 10 38 24

样例输出

14

数据范围

• $1\le k\le 2.5\times 10^5$；
• $k\le n\le 10^{14}$；
• 对于所有 $1\le i\le k$，均有 $0\le m_i<n$；
• $m_1,m_2,\ldots,m_k$ 两两不同；
• 约 $70\%$ 的测试数据满足 $k\le 10^3$；
• 约 $20\%$ 的测试数据还满足 $n<10^8$ 且 $k\le 100$；
• 时间限制为 $3\times 10^4\ \mathrm{ms}$；
• 内存限制为 $3.2768\times 10^4\ \mathrm{KB}$。

来源与许可

本题为 POI 2011 试题「Strongbox」，题面与测试数据整理自 BZOJ 2277。

样例 1

输入

42 5
28 31 10 38 24

输出

14