给定一个正整数 $N$ 和一个长度为 $M$ 的整数序列 $A$。

对于 $0$ 到 $N-1$ 之间的整数 $x$，我们定义 $f(x)$ 为：

• 满足 $\sum\limits_{i=1}^M A_i B_i \equiv x \pmod N$ 的所有长度为 $M$ 的整数序列 $B$ 中，$\sum\limits_{i=1}^M |B_i|$ 的最小值。

在题目的约束条件下，可以保证对于任意 $x$ 都至少存在一个满足 $\sum\limits_{i=1}^M A_i B_i \equiv x \pmod N$ 的整数序列 $B$。请在 $x=0,1,\dots,N-1$ 中，求出能够使 $f(x)$ 达到最大的 $x$。若有多个 $x$ 均能取得最大值，输出其中最小的一个。

输入由一行组成，格式如下：

$N$ $M$ $A_1$ $A_2$ $\dots$ $A_M$

请你输出一个整数，表示使 $f(x)$ 最大的 $x$。如果有多个这样的 $x$，输出最小的一个。

子任务

1. （1 分）$NM \leq 200{,}000$
2. （99 分）无其他额外限制

样例解释 1

$f(0)=0, f(1)=1, f(2)=2, f(3)=1$，因此答案为 $2$。

此测试点满足子任务 1 的约束。

样例解释 2

此测试点满足子任务 1 的约束。

数据范围

• $1 \leq M \leq N \leq 200{,}000$
• $1 = A_1 < A_2 < \dots < A_M \leq N$
• 所有输入均为整数。

由 ChatGPT 5 翻译