Strongbox

Byteasar tests and certifies anti-burglary devices. He has just received a new kind of strongbox to test: a combinatorial safe. It is opened with a rotary dial, just like an ordinary combination safe, but the way it opens is different.

The dial can be set to $n$ different positions, numbered $0$ to $n-1$. Some of these positions open the safe and the others do not. The set of opening positions has the following combinatorial property, which gives the safe its name: if $x$ and $y$ are both opening positions, then $(x + y) \bmod n$ is an opening position as well. This holds for $x = y$ too.

Byteasar tried $k$ distinct positions $m_1, m_2, \ldots, m_k$. The first $k-1$ of them, $m_1, m_2, \ldots, m_{k-1}$, did not open the safe; only the last one, $m_k$, did. He does not intend to try any of the remaining positions. Using only what he has learned from the positions he tried, determine the maximum possible number of positions that open the safe.

The first line contains two integers $n$ and $k$ separated by a single space, where $1 \le k \le 250\,000$ and $k \le n \le 10^{14}$.

The second line contains $k$ distinct integers $m_1, m_2, \ldots, m_k$ separated by single spaces, where $0 \le m_i < n$.

The input is guaranteed to correspond to some combinatorial safe consistent with the description above: there exists a safe that positions $m_1, \ldots, m_{k-1}$ do not open and position $m_k$ does.

Print a single integer: the maximum number of dial positions that can open the safe.