D - Placement of Street Lights Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君が住む町には、東西にまっすぐ伸びる一本道があります。この道には N 個の街灯の設置箇所が一列に並んでおり、西から順に地点 1 、地点 2 、…、地点 N と番号が付けられています。

現在、 M 個の設置箇所に街灯が点灯しています。街灯 i （ 1 \leq i \leq M ）は地点 S_i に設置されています。すべての街灯は異なる地点に設置されていることが保証されています。

高橋君は、道の暗い区間をなるべく短くしたいと考えています。具体的には、街灯が設置されている地点の番号を小さい順に並べたとき、隣り合う街灯の地点番号の差の最大値を「最大暗区間」と定義します。

ただし、街灯が 1 個しかない場合は、最大暗区間を 0 とします。

高橋君は、点灯中の街灯のうちちょうど 1 つを選び、その街灯を現在の地点から別の空いている設置箇所に移設することができます（移設しないという選択はできません。必ずちょうど 1 つの街灯を別の空き地点に移設します）。この操作を行った後の最大暗区間の最小値を求めてください。

制約

  • 3 \leq N \leq 3 \times 10^5
  • 2 \leq M \leq N - 1
  • 1 \leq S_i \leq N （ 1 \leq i \leq M ）
  • S_i はすべて異なる
  • 入力はすべて整数

入力

N M
S_1 S_2 \cdots S_M
  • 1 行目には、設置箇所の数を表す N と、街灯の数を表す M が、スペース区切りで与えられる。
  • 2 行目には、各街灯が設置されている地点番号 S_1, S_2, \ldots, S_M が、スペース区切りで与えられる。

出力

ちょうど 1 つの街灯を空き地点に移設した後の最大暗区間の最小値を 1 行で出力せよ。

入力例 1

10 4
2 6 9 4

出力例 1

2

入力例 2

7 3
1 4 7

出力例 2

2

入力例 3

50 12
3 8 15 16 23 31 37 40 41 45 48 50

出力例 3

7

入力例 4

200 35
2 7 13 19 25 31 38 44 51 58 66 73 81 90 99 108 117 126 135 144 153 161 168 174 180 185 189 192 194 196 197 198 199 200 1

出力例 4

9

入力例 5

3 2
1 2

出力例 5

1

Score : 400 pts

Problem Statement

In the town where Takahashi lives, there is a straight road running from east to west. Along this road, there are N installation spots for street lights lined up in a row, numbered from west to east as point 1, point 2, …, point N.

Currently, street lights are lit at M installation spots. Street light i (1 \leq i \leq M) is installed at point S_i. It is guaranteed that all street lights are installed at distinct points.

Takahashi wants to minimize the dark sections of the road. Specifically, when the point numbers where street lights are installed are sorted in ascending order, the maximum difference between the point numbers of adjacent street lights is defined as the "maximum dark interval."

However, if there is only one street light, the maximum dark interval is defined as 0.

Takahashi can choose exactly one of the currently lit street lights and relocate it from its current point to another empty installation spot (choosing not to relocate is not an option; exactly one street light must be relocated to a different empty point). Find the minimum possible value of the maximum dark interval after this operation.

Constraints

  • 3 \leq N \leq 3 \times 10^5
  • 2 \leq M \leq N - 1
  • 1 \leq S_i \leq N (1 \leq i \leq M)
  • All S_i are distinct
  • All inputs are integers

Input

N M
S_1 S_2 \cdots S_M
  • The first line contains N, the number of installation spots, and M, the number of street lights, separated by a space.
  • The second line contains the point numbers S_1, S_2, \ldots, S_M where each street light is installed, separated by spaces.

Output

Print in one line the minimum possible value of the maximum dark interval after relocating exactly one street light to an empty point.

Sample Input 1

10 4
2 6 9 4

Sample Output 1

2

Sample Input 2

7 3
1 4 7

Sample Output 2

2

Sample Input 3

50 12
3 8 15 16 23 31 37 40 41 45 48 50

Sample Output 3

7

Sample Input 4

200 35
2 7 13 19 25 31 38 44 51 58 66 73 81 90 99 108 117 126 135 144 153 161 168 174 180 185 189 192 194 196 197 198 199 200 1

Sample Output 4

9

Sample Input 5

3 2
1 2

Sample Output 5

1