Flatland Space Stations

Flatland has n cities in a line (0 to n-1). Some cities have space stations. Find the maximum distance from any city to its nearest space station. Example: n=5, stations at [0,4]. City 0: distance 0, City 1: min(1,3)=1, City 2: min(2,2)=2, City 3: min(3,1)=1, City 4: distance 0. Maximum is 2.

Input

First line: n m (space-separated, m is number of stations). Second line: m space-separated integers (city indices with stations).

Output

A single integer: the maximum distance to nearest space station.

Sample

5 2
0 4

Expected

2