AT_oupc2023_day1_i Min!? Max!? Max!? Min!?

给定一个正整数 $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 翻译