Strongbox

바이테아사르(Byteasar)는 도난 방지 장치를 시험하고 인증하는 일을 한다. 그는 새로운 종류의 금고를 시험용으로 받았는데, 바로 조합 금고(combinatorial safe)이다. 회전식 다이얼로 여는 점은 보통의 다이얼 금고와 같지만, 열리는 방식이 다르다.

다이얼은 $0$번부터 $n-1$번까지 번호가 매겨진 $n$가지 위치로 맞출 수 있다. 이 위치들 중 일부는 금고를 열고, 나머지는 열지 못한다. 금고를 여는 위치들의 집합에는 다음과 같은 조합적 성질이 있으며, 금고의 이름도 여기서 비롯된다. 즉, $x$와 $y$가 모두 여는 위치라면 $(x + y) \bmod n$ 역시 여는 위치이다. 이 성질은 $x = y$인 경우에도 성립한다.

바이테아사르는 서로 다른 $k$개의 위치 $m_1, m_2, \ldots, m_k$를 시도했다. 이 중 앞의 $k-1$개 $m_1, m_2, \ldots, m_{k-1}$로는 금고가 열리지 않았고, 오직 마지막 위치 $m_k$로만 열렸다. 그는 남은 위치를 더 시도할 생각이 없다. 그가 시도해 본 위치들로부터 알 수 있는 정보만으로, 금고를 열 수 있는 위치의 최대 개수를 구하여라.

첫째 줄에 두 정수 $n$과 $k$가 공백 하나로 구분되어 주어진다. $1 \le k \le 250\,000$이고 $k \le n \le 10^{14}$이다.

둘째 줄에 서로 다른 $k$개의 정수 $m_1, m_2, \ldots, m_k$가 공백 하나로 구분되어 주어진다. $0 \le m_i < n$이다.

입력은 항상 위 설명을 만족하는 어떤 조합 금고에 대응하도록 주어진다. 즉, 위치 $m_1, \ldots, m_{k-1}$로는 열리지 않고 위치 $m_k$로는 열리는 금고가 반드시 존재한다.

금고를 열 수 있는 다이얼 위치의 최대 개수를 정수 하나로 첫째 줄에 출력한다.