Gossip

Problem

1からnまでの番号が順番に割り当てられているn人のアイドルが横一列に並んでいる。
アイドルiは単位時間でアイドルi-1とアイドルi+1に情報を伝達することができる。ただし、アイドル1はアイドル2にしか情報を伝達できず、アイドルnはアイドルn-1にしか情報を伝達できない。

時刻0の時点で、番号がa₁, a₂, ..., a_mであるm人のアイドルが秘密の情報を持っている。すべてのアイドルが秘密の情報を得ることのできる最小の時間を求めよ。

Input

入力は以下の形式で与えられる。

n m
a1 a2 ... am

1行目に2つの整数nとmが空白区切りで与えられる。
2行目にm個の整数a₁, a₂, ..., a_mが空白区切りで与えられる。

Constraints

• 2 ≤ n ≤ 10⁵
• 1 ≤ m ≤ n
• 1 ≤ a_i ≤ n
• a_iの値は全て異なる
• a_iは昇順で与えられる

Output

すべてのアイドルに情報が伝わる最小の時間を1行に出力する。

Sample Input 1

3 2
1 3

Sample Output 1

1

Sample Input 2

10 3
2 5 7

Sample Output 2

3

Sample Input 3

10 5
2 5 6 8 10

Sample Output 3

1

Sample Input 4

100000 1
1

Sample Output 4

99999

Note

Link

 

---