样例下载

题目描述

Alice 有一个盒子，里面装着一些小球，每个小球上写着一个号码，任意两个小球写着的号码均不相同。

Bob 尝试猜盒子里的小球写的号码。Alice 只告诉他两个条件：

（1）所有号码均为小于 n 的非负整数。

（2）如果号码 x, y 在盒子里，那么号码 (x+y)%n 也在盒子里。其中 % 表示取模，并且 x 和 y 可以相同。

Bob 猜了 m 次，终于在最后一次猜对了。

问：盒子里最多装着多少个小球？

输入格式

第一行：包含两个整数 $n, m$。

第二行：包含 $m$ 个非负整数 $X_i$，依次表示 Bob 猜的 $m$ 个号码，其中前 $m-1$ 个号码都不在盒子里，最后一个号码在盒子里。

输出格式

一个整数，表示答案。

样例输入

42 5
28 31 10 38 24

样例输出

14

数据范围

$20\%$ 的数据，满足 $1 ≤ m ≤ 100,n ≤ 10^8$。

$70\%$ 的数据，满足 $1 ≤ m ≤ 1000$。

$100\%$ 的数据，满足 $1 ≤ m ≤ 3 × 10^5, m ≤ n ≤ 10^{14}, 0 ≤ X_i <n$。输入数据保证不会出现矛盾，即保证有解。