問題文

正整数 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 のうち一番小さいものを求めてください。

制約

• 1 \leq M \leq N \leq 200{,}000
• 1 = A_1 < A_2 < \dots < A_M \leq N
• 入力はすべて整数

小課題

1. (1 点) NM \leq 200{,}000

2. (99 点) 追加の制約はない

入力例 1

4 1
1

出力例 1

2

f(0)=0,f(1)=1,f(2)=2,f(3)=1 なので答えは 2 になります。

このテストケースは小課題 1 の制約を満たします。

入力例 2

6 2
1 2

出力例 2

3

このテストケースは小課題 1 の制約を満たします。