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| $ の最小値 なお、制約の条件下で、 $ \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 $

答えを $ 1 $ 行で出力してください。

### 小課題 1. ( $ 1 $ 点) $ NM \leq 200{,}000 $ 2. ( $ 99 $ 点) 追加の制約はない ### Sample Explanation 1 $ f(0)=0,f(1)=1,f(2)=2,f(3)=1 $ なので答えは $ 2 $ になります。 このテストケースは小課題 1 の制約を満たします。 ### Sample Explanation 2 このテストケースは小課題 1 の制約を満たします。 ### Constraints - $ 1 \leq M \leq N \leq 200{,}000 $ - $ 1 = A_1 < A_2 < \dots < A_M \leq N $ - 入力はすべて整数