Flatland is a country with a number of cities, some of which have space stations.  Cities are numbered consecutively and each has a road of $1km$ length connecting it to the next city.  It is not a circular route, so the first city doesn't connect with the last city.  Determine the maximum distance from any city to its nearest space station.

Example 

$n=3$ 

$\boldsymbol{c}=[1]$   

There are $n=3$ cities and city $1$ has a space station.  They occur consecutively along a route.  City $\mbox{o}$ is $1-0=1$ unit away and city $2$ is $2-1=1$ units away.  City $1$ is $0$ units from its nearest space station as one is located there.  The maximum distance is $1$.

Function Description  

Complete the flatlandSpaceStations function in the editor below.   

flatlandSpaceStations has the following parameter(s):  

int n: the number of cities  
int c[m]: the indices of cities with a space station   

Returns 

- int: the maximum distance any city is from a space station  

Input Format

The first line consists of two space-separated integers, $n$ and $m$. 

The second line contains $m$ space-separated integers, the indices of each city that has a space-station. These values are unordered and distinct.

Constraints

$1\leq n\leq10^5$
$1\leq m\leq n$
There will be at least $1$ city with a space station.
No city has more than one space station.

Output Format

Sample Input 0

STDIN   Function
-----   --------
5 2     n = 5, c[] size m = 2
0 4     c = [0, 4]

Sample Output 0

2

Explanation 0

This sample corresponds to following graphic:  

The distance to the nearest space station for each city is listed below:

$c\left[\textbf{0}\right]$ has distance $0 km$, as it contains a space station.
$c\left[1\right]$ has distance $1\ km$ to the space station in $c\left[\textbf{0}\right]$.
$c[2]$ has distance $2km$ to the space stations in $c\left[\textbf{0}\right]$ and $c\left[4\right]$.
$c[3]$ has distance $1\ km$ to the space station in $c\left[4\right]$.
$c\left[4\right]$ has distance $0 km$, as it contains a space station.

We then take $max(0,1,2,1,0)=2$.

Sample Input 1

6 6
0 1 2 4 3 5

Sample Output 1

0

Explanation 1

In this sample, $n=m$ so every city has space station and we print $0$ as our answer.

Difficulty: EASY
Tags: Implementation

Starter code:

Solutions:
import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c = sorted(c)
if m == 1:
	print(max(c[0] - 0, n - 1 - c[0]))
else:
	gaps = []
	for i in range(1, m):
		gaps.append(c[i] - c[i - 1])
	print(max(c[0] - 0, n - 1 - c[-1], max(gaps) // 2))


from bisect import bisect_left

def closest(xs, x):
	pos = bisect_left(xs, x)
	if pos == 0:
		return xs[0]
	if pos == len(xs):
		return xs[-1]
	before = xs[pos - 1]
	after = xs[pos]
	if after - x < x - before:
		return after
	else:
		return before
(n, m) = map(int, input().split())
c = list(map(int, input().split()))
c.sort()
max = 0
for i in range(n):
	d = abs(i - closest(c, i))
	if d > max:
		max = d
print(max)


import sys
(n, m) = list(map(int, input().split()))
c = list(map(int, input().split()))
c.sort()
if len(c) > 1:
	d = max([c[i] - c[i - 1] for i in range(1, len(c))]) // 2
else:
	d = 0
print(max(d, c[0], n - 1 - c[len(c) - 1]))


def main():
	(n, m) = map(int, input().split())
	c = list(map(int, input().split()))
	l = [10 ** 5] * n
	for x in c:
		l[x] = 0
	for i in range(1, len(l)):
		if l[i] == 0:
			continue
		else:
			l[i] = min(l[i], l[i - 1] + 1)
	for i in range(len(l) - 2, -1, -1):
		if l[i] == 0:
			continue
		else:
			l[i] = min(l[i], l[i + 1] + 1)
	print(max(l))
main()


(n, m) = map(int, input().split())
s = set(map(int, input().split()))
l = [float('inf')] * n
p = -float('inf')
for i in range(n):
	if i in s:
		p = i
	l[i] = i - p
r = [float('inf')] * n
p = float('inf')
for i in reversed(range(n)):
	if i in s:
		p = i
	r[i] = p - i
dist = [min(l[i], r[i]) for i in range(n)]
print(max(dist))


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c.sort()
k = max(c[0], n - c[-1] - 1)
if len(c) > 1:
	print(max(k, max([int((i - j) / 2) for (i, j) in zip(c[1:], c[:-1])])))
else:
	print(k)


(n, m) = map(int, input().split())
a = sorted(map(int, input().split()))
ans = max(a[0], n - a[-1] - 1)
for i in range(1, m):
	ans = max(ans, (a[i] - a[i - 1]) // 2)
print(ans)


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c = sorted(c)
diff = []
for (i, j) in zip(c, c[1:]):
	diff.append((j - i) // 2)
diff.append(c[0])
diff.append(n - 1 - c[-1])
print(max(diff))


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c.sort()
maxgap = max((a - b for (a, b) in zip(c[1:], c))) if len(c) > 1 else 0
ans = max(maxgap // 2, c[0], n - 1 - c[-1])
print(ans)


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
max = 0
c.sort()
for i in range(1, m):
	if c[i] - c[i - 1] > max:
		max = c[i] - c[i - 1]
max = max // 2
if max <= c[0]:
	max = c[0]
if max < n - 1 - c[m - 1]:
	max = n - 1 - c[m - 1]
print(max)


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c.sort()
dif = 0
if n > 1:
	for i in range(1, m):
		if c[i] - c[i - 1] > dif:
			dif = c[i] - c[i - 1]
	dif = dif // 2
	dif = max(dif, c[0])
	dif = max(dif, n - 1 - c[m - 1])
print(dif)


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
space = [False for _ in range(n)]
for nn in c:
	space[nn] = True
left = [0 for _ in range(n)]
cnt = n + 1
for i in range(n):
	if space[i]:
		cnt = 0
	else:
		cnt += 1
	left[i] = cnt
cnt = n + 1
i = n
for _ in range(n):
	i -= 1
	if space[i]:
		cnt = 0
	else:
		cnt += 1
	left[i] = min(left[i], cnt)
print(max(left))


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c.sort()

def get_next_dist(pos, next_c):
	if next_c >= m:
		return n
	return c[next_c] - pos

def get_prev_dist(pos, prev_c):
	if prev_c < 0:
		return n
	return pos - c[prev_c]
distance_to_last_station = n
prev_station = -1
next_station = 0
next_pos = c[0]
min_distance = []
for pos in range(n):
	if pos == next_pos:
		prev_station += 1
		next_station += 1
		if next_station < m:
			next_pos = c[next_station]
		else:
			next_station = n
	next_dist = get_next_dist(pos, next_station)
	prev_dist = get_prev_dist(pos, prev_station)
	min_distance.append(min(next_dist, prev_dist))
print(max(min_distance))


import math
(n, m) = map(int, input().split())
space = list(map(int, input().split()))
space.sort()
max = 0
prev = 0
j = 0
divide = False
for i in range(0, n):
	if space[j] == i:
		if divide:
			result = math.ceil(prev / 2)
		else:
			result = prev
		if result > max:
			max = result
		prev = 0
		divide = True
		if j < m - 1:
			j += 1
	else:
		prev = prev + 1
if prev > max:
	max = prev
print(max)


(n, m) = map(int, input().split())
stations = sorted(list(map(int, input().split())))
max1 = max(stations[0], n - 1 - stations[-1])
maxx = 0
start = stations[0]
for i in stations[1:]:
	k = i - start - 1
	if k > maxx:
		maxx = k
	start = i
print(max(maxx % 2 + maxx // 2, max1))


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
t = [False for i in range(n)]
dist = [1000000 for i in range(n)]
for j in range(m):
	t[c[j]] = True
maxi = 0
last = -1000000
for i in range(n):
	if t[i]:
		last = i
	dist[i] = min(dist[i], i - last)
last = 1000000
for ii in range(n):
	i = n - 1 - ii
	if t[i]:
		last = i
	dist[i] = min(dist[i], last - i)
maxi = 0
for i in dist:
	maxi = max(maxi, i)
print(maxi)


(n, m) = map(int, input().split())
ss = list(map(int, input().split()))
ss.sort()
ans = max(ss[0], n - 1 - ss[-1])
for i in range(m - 1):
	ans = max(ans, (ss[i + 1] - ss[i]) // 2)
print(ans)


import sys
(n, m) = map(int, input().split(' '))
arr = list(map(int, input().split(' ')))
arr.sort()
mdist = 0
dist = []
for i in range(1, m):
	dist.append((arr[i] - arr[i - 1]) / 2)
	if mdist < (arr[i] - arr[i - 1]) / 2:
		mdist = (arr[i] - arr[i - 1]) / 2
if arr[0] > mdist:
	mdist = arr[0]
if abs(arr[m - 1] - n + 1) > mdist:
	mdist = abs(arr[m - 1] - n + 1)
print(int(mdist))


from math import floor
from sys import stderr
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c.sort()
print(c, file=stderr)
maxi = c[0]
i = 0
for i in range(1, m):
	maxi = max(floor((c[i] - c[i - 1]) / 2), maxi)
maxi = max(n - c[i] - 1, maxi)
print(maxi, file=stderr)
print(maxi)


(n, m) = tuple(map(int, input().strip().split()))
cs = list(map(int, input().strip().split()))
cs.sort()
maximaDistancia = 0 if m <= 1 else max([abs(cs[i] - cs[i + 1]) // 2 for i in range(m - 1)])
print(max(maximaDistancia, cs[0], n - 1 - cs[-1]))


import math
(n, m) = map(int, input().strip().split(' '))
c = set(map(int, input().strip().split(' ')))
(min_left, min_right) = ([0] * (n + 1), [0] * (n + 1))
min_left[0] = n + 2
min_right[-1] = n + 2
for i in range(n):
	if i in c:
		min_left[i + 1] = 0
	else:
		min_left[i + 1] = min_left[i] + 1
for i in range(n - 1, -1, -1):
	if i in c:
		min_right[i] = 0
	else:
		min_right[i] = min_right[i + 1] + 1
closest = [min(x) for x in zip(min_left[1:], min_right[:-1])]
print(max(closest))


import sys
from bisect import bisect_left

def takeClosest(myList, myNumber):
	pos = bisect_left(myList, myNumber)
	if pos == 0:
		return myList[0]
	if pos == len(myList):
		return myList[-1]
	before = myList[pos - 1]
	after = myList[pos]
	if after - myNumber < myNumber - before:
		return after
	else:
		return before
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c.sort()
distances = [abs(i - takeClosest(c, i)) for i in range(n)]
print(max(distances))


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c.sort()
mx = 0
if 0 not in c:
	mx = c[0]
if n - 1 not in c:
	if n - c[-1] > mx:
		mx = n - c[-1] - 1
for med in map(lambda x: int((x[1] - x[0]) / 2), zip(c, c[1:])):
	if med > mx:
		mx = med
print(mx)


from math import floor
import sys

def maxDist(n, m, c):
	if m is n:
		return '0'
	max = c[0]
	for i in range(m - 1):
		val = floor((c[i + 1] - c[i]) / float(2))
		if val > max:
			max = val
	if max > n - 1 - c[m - 1]:
		return str(max)
	else:
		return str(n - 1 - c[m - 1])
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = sorted([int(c_temp) for c_temp in input().strip().split(' ')])
print(maxDist(n, m, c))


def main():
	(cities_no, space_stations_no) = map(int, input().strip().split())
	space_station_cities = sorted(map(int, input().strip().split()))
	if len(space_station_cities) > 1:
		max_distance = max(map(lambda x, y: (y - x) // 2, space_station_cities[:-1], space_station_cities[1:]))
	else:
		max_distance = 0
	print(max(max_distance, space_station_cities[0] - 0, cities_no - 1 - space_station_cities[-1]))
main()


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c.sort()
k = 0
for i in range(m - 1):
	k = max(k, int((c[i + 1] - c[i]) / 2))
k = max(k, int(c[0]), int(n - 1 - c[m - 1]))
print(k)


import sys
(n, m) = [int(x) for x in input().strip().split(' ')]
c = sorted([int(c_temp) for c_temp in input().strip().split(' ')])
(j, dists) = (0, [])
for i in range(n):
	if j < m and i == c[j]:
		(d, j) = (0, j + 1)
	elif j in [0, m]:
		d = c[0] - i if j == 0 else i - c[-1]
	else:
		d = min(c[j] - i, i - c[j - 1])
	dists.append(d)
print(max(dists))


import sys
import math
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c.sort()
min_dist = 0
dist = int(math.floor(c[0] - 0))
if dist > min_dist:
	min_dist = dist
dist = int(math.floor(n - 1 - c[m - 1]))
if dist > min_dist:
	min_dist = dist
for j in range(m - 1):
	dist = int(math.floor((c[j + 1] - c[j]) / 2.0))
	if dist > min_dist:
		min_dist = dist
print(min_dist)


import sys
from math import floor
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
stations = sorted(c)
longest = max(n - 1 - stations[-1], stations[0])
for (index, i) in enumerate(stations[:-1]):
	longest = max(longest, floor((stations[index + 1] - i) / 2))
print(longest)


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c.sort()
res = c[0]
for i in range(1, m):
	prev = c[i - 1]
	curr = c[i]
	res = max(res, (curr - prev) // 2)
res = max(res, n - 1 - c[-1])
print(res)


import sys
(cities, stations) = map(int, input().strip().split(' '))
has_station = [False] * cities
for index in map(int, input().strip().split(' ')):
	has_station[index] = True
worst = 0
closest_left = 0 if has_station[0] else -1
try:
	closest_right = has_station[1:].index(True) + 1
except ValueError:
	closest_right = -1
for i in range(cities):
	if has_station[i]:
		closest_left = i
		try:
			closest_right = has_station[i + 1:].index(True) + i + 1
		except ValueError:
			closest_right = -1
		continue
	closer = 999999999
	if closest_left != -1:
		closer = i - closest_left
	if closest_right != -1:
		closer = min(closer, closest_right - i)
	worst = max(worst, closer)
print(worst)


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c.sort()
if n == m:
	print(0)
else:
	r = []
	if 0 not in c:
		r += [c[0]]
	if n - 1 not in c:
		r += [n - 1 - c[-1]]
	for i in range(m - 1):
		r += [(c[i + 1] - c[i]) // 2]
	print(max(r))


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
if len(c) == n:
	print(0)
else:
	ans = 0
	c.sort()
	thresh = 0
	ans = 0
	for i in range(n):
		if thresh + 1 < m:
			temp = abs(c[thresh + 1] - i)
			temp1 = abs(c[thresh] - i)
			if temp1 > temp:
				thresh += 1
				ans = max(temp, ans)
			else:
				ans = max(temp1, ans)
		else:
			t = abs(c[thresh] - i)
			ans = max(ans, t)
	print(ans)


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = sorted([int(c_temp) for c_temp in input().strip().split(' ')])
diffs = []
for i in range(len(c) - 1):
	diffs.append((c[i + 1] - c[i]) // 2)
diffs.append(c[0])
diffs.append(n - 1 - c[-1])
print(max(diffs))


import sys

def getLeftDistance(first_city_with_space_station):
	return first_city_with_space_station - 0

def getRightDistance(number_of_cities, last_city_with_space_station):
	last_city_id = number_of_cities - 1
	return last_city_id - last_city_with_space_station

def getMaxInnerDistance(number_of_cities, cities_with_space_stations):
	max_distance = 0
	for index in range(1, len(cities_with_space_stations)):
		first_city = cities_with_space_stations[index - 1]
		second_city = cities_with_space_stations[index]
		max_distance = max(max_distance, (second_city - first_city) // 2)
	return max_distance

def main():
	(number_of_cities, _number_of_space_stations) = input().strip().split(' ')
	number_of_cities = int(number_of_cities)
	sorted_cities_with_space_stations = sorted([int(city_id) for city_id in input().strip().split(' ')])
	largest_left_distance = getLeftDistance(sorted_cities_with_space_stations[0])
	largest_inner_distance = getMaxInnerDistance(number_of_cities, sorted_cities_with_space_stations)
	largest_right_distance = getRightDistance(number_of_cities, sorted_cities_with_space_stations[-1])
	print(max(largest_left_distance, largest_inner_distance, largest_right_distance))
main()


(n, m) = map(int, input().strip().split())
c = list(map(int, input().strip().split()))
c.sort()
ans = c[0] - 0
for i in range(1, m):
	temp = (c[i] - c[i - 1]) // 2
	ans = max(ans, temp)
ans = max(ans, n - 1 - c[m - 1])
print(ans)


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c.sort()
if m == 1 and n == 1:
	print(0)
	sys.exit()
max_ = 0
for (i, j) in enumerate(c[:-1]):
	dist = (c[i + 1] - c[i]) // 2
	if max_ < dist:
		max_ = dist
dist = c[0] - 0
if max_ < dist:
	max_ = dist
dist = n - 1 - c[-1]
if max_ < dist:
	max_ = dist
print(max_)


import sys
(cities, space_stations) = tuple((int(x) for x in input().strip().split()))
stations_locations = set((int(x) for x in input().strip().split()))
road = [x in stations_locations for x in range(cities)]
highest = 0
current = 0
flag_possible_inside = False
for (i, city) in enumerate(road):
	if not flag_possible_inside:
		if city is False:
			current += 1
			if current >= highest:
				highest = current
		else:
			flag_possible_inside = True
			current = 0
	elif city is False:
		current += 1
	else:
		if current % 2 == 0:
			beetween = current // 2
		else:
			beetween = current // 2 + 1
		if beetween >= highest:
			highest = beetween
		current = 0
else:
	if road[-1] is False and flag_possible_inside:
		if current >= highest:
			highest = current
print(highest)


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
if n == m:
	print(0)
else:
	distances = []
	c.sort()
	if c[-1] != n - 1:
		distances.append(n - c[-1] - 1)
	if c[0] != 0:
		distances.append(c[0])
	for i in range(m - 1):
		distances.append((c[i + 1] - c[i]) // 2)
	print(max(distances))


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = list(map(int, input().strip().split(' ')))
if n == m:
	ans = 0
else:
	c = list(c)
	c.sort()
	temp = n - c[m - 1] - 1
	if c[0] > temp:
		ans = c[0]
	else:
		ans = temp
	for i in range(1, m):
		temp = c[i] - c[i - 1]
		temp = temp / 2
		if ans < temp:
			ans = temp
print(int(ans))


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
arr1 = [-1 for i in range(n)]
arr2 = [-1 for i in range(n)]
for x in c:
	arr1[x] = 0
	arr2[x] = 0
arr2 = list(reversed(arr2))
dist1 = 1
i = arr1.index(0)
while i < n:
	if arr1[i] == -1:
		arr1[i] = dist1
		dist1 += 1
	else:
		dist1 = 1
	i += 1
dist1 = 1
i = arr2.index(0)
while i < n:
	if arr2[i] == -1:
		arr2[i] = dist1
		dist1 += 1
	else:
		dist1 = 1
	i += 1
arr2 = list(reversed(arr2))
final_arr = [0 for i in range(n)]
for i in range(n):
	if arr1[i] == -1:
		final_arr[i] = arr2[i]
	elif arr2[i] == -1:
		final_arr[i] = arr1[i]
	else:
		final_arr[i] = min([arr1[i], arr2[i]])
print(max(final_arr))


def MAX(a, b):
	if a > b:
		return a
	else:
		return b
import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c.sort()
i = 0
ma = c[0] - 0
if len(c) > 1:
	while i < len(c):
		a = c[i]
		if i + 1 < len(c):
			b = c[i + 1]
			l = int((b - a) / 2)
			ma = MAX(ma, l)
		else:
			b = n - 1 - a
			ma = MAX(ma, b)
		i = i + 1
else:
	a = c[0] - 0
	b = n - 1 - c[0]
	ma = MAX(a, b)
print(ma)


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c.sort()
d = c[0] - 0
for i in range(len(c) - 1):
	if (c[i + 1] - c[i]) // 2 > d:
		d = (c[i + 1] - c[i]) // 2
if n - 1 - c[len(c) - 1] > d:
	print(n - 1 - c[len(c) - 1])
else:
	print(d)


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = sorted([int(c_temp) for c_temp in input().strip().split(' ')])
o = []
(prev, nex) = (None, c[0])
(nex_idx, prev_idx) = (0, 0)
for i in range(n):
	if prev_idx < len(c) and i == c[prev_idx]:
		prev = i
		prev_idx += 1
	if nex is None or nex < i:
		nex_idx += 1
		if nex_idx < len(c):
			nex = c[nex_idx]
		else:
			nex = None
	if prev is not None:
		if nex is None:
			o.append(i - prev)
		else:
			o.append(min(i - prev, nex - i))
	elif nex is not None:
		if prev is None:
			o.append(nex - i)
		else:
			o.append(min(i - prev, nex - i))
print(max(o))


(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
space_stations = set(c)
left_right_min = []
curr = float('inf')
for i in range(n):
	if i in space_stations:
		curr = -1
	curr = curr + 1
	left_right_min.append([curr, None])
curr = float('inf')
for i in range(n - 1, -1, -1):
	if i in space_stations:
		curr = -1
	curr = curr + 1
	left_right_min[i][1] = curr
maximum = float('inf') * -1
for i in range(len(left_right_min)):
	curr_min = min(left_right_min[i])
	if curr_min > maximum:
		maximum = curr_min
print(maximum)


import sys
(n, m) = input().strip().split(' ')
(n, m) = (int(n), int(m))
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c.sort()
md = max(c[0], n - 1 - c[len(c) - 1])
for i in range(len(c) - 1):
	md = max(md, (c[i + 1] - c[i]) // 2)
print(md)


import sys
import math
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = sorted([int(c_temp) for c_temp in input().strip().split(' ')])
maxDist = 0
for i in range(len(c) - 1):
	maxDist = max(maxDist, (c[i + 1] - c[i]) // 2)
maxDist = max(maxDist, c[0], n - 1 - c[-1])
print(maxDist)


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
if len(c) == 1:
	print(max(c[0], n - c[0] - 1))
else:
	c.sort()
	p = 0
	for i in range(1, len(c)):
		p = max(p, c[i] - c[i - 1])
	print(max(int(p / 2), c[0], n - c[m - 1] - 1))


(n, m) = list(map(int, input().split()))
ar = sorted(list(map(int, input().split())))
t = max(ar[0], n - ar[len(ar) - 1] - 1)
for x in range(1, len(ar)):
	t = max(t, (ar[x] + ar[x - 1]) // 2 - ar[x - 1])
print(t)


import sys
(n, m) = input().strip().split(' ')
(n, m) = (int(n), int(m))
cs = [int(c_temp) for c_temp in input().strip().split(' ')]
cs = sorted(cs)
max_dist = cs[0]
for i in range(1, len(cs)):
	max_dist = max(max_dist, (cs[i] - cs[i - 1]) // 2)
max_dist = max(max_dist, n - 1 - cs[-1])
print(max_dist)


import sys, math
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = sorted([int(c_temp) for c_temp in input().strip().split(' ')])
maxDistanceBetweenStations = max((c[i + 1] - c[i] for i in range(0, m - 1))) if m > 1 else c[0]
maxDistanceToStation = int(math.floor(maxDistanceBetweenStations / 2))
maxDistanceToStation = max(maxDistanceToStation, n - 1 - c[-1])
maxDistanceToStation = max(maxDistanceToStation, c[0])
print(maxDistanceToStation)


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c.sort()
left_length = c[0]
right_length = n - 1 - c[m - 1]
mid_length = 0
for i in range(1, m):
	if c[i] - c[i - 1] - 1 > mid_length:
		mid_length = c[i] - c[i - 1] - 1
mid_length = (mid_length + 1) // 2
print(max(left_length, right_length, mid_length))


import sys
import math
(n, m) = list(map(int, input().split()))
c = [int(x) for x in input().split()]
c.sort()
max_distance = c[0]
diff = 0
for x in range(1, m):
	tmp = c[x] - c[x - 1]
	if tmp > 1 and tmp > diff:
		diff = tmp
max_distance = max(max_distance, math.floor(diff / 2))
if c[m - 1] != n - 1:
	max_distance = max(max_distance, n - c[m - 1] - 1)
print(max_distance)


(n, m) = (int(_) for _ in input().split())
a = sorted([int(_) for _ in input().split()])
c = [-a[0]]
c.extend(a)
c.append(2 * n - c[-1] - 1)
ans = 0
for i in range(len(c) - 1):
	ans = max(ans, (c[i + 1] - c[i]) // 2)
print(ans)


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c = sorted(c)
d_l = c[0]
d_r = n - 1 - c[-1]
difs = []
for x in range(0, m - 1):
	difs.append((c[x + 1] - c[x]) / 2)
if m > 1:
	dist = int(max(difs))
	print(max(d_l, d_r, dist))
else:
	print(max(d_l, d_r))


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
stations = [int(c_temp) for c_temp in input().strip().split(' ')]
stations.sort()
r = max(stations[0], n - stations[m - 1] - 1)
last = stations[0]
for i in range(1, m):
	r = max(r, (stations[i] - last) // 2)
	last = stations[i]
print(r)


import sys

def main():
	(n, m) = [int(s) for s in input().strip().split(' ')]
	spaceCities = [int(sc) for sc in input().strip().split(' ')]
	spaceCities.sort()
	maxInBet = 0
	for i in range(0, len(spaceCities) - 1):
		d = int((spaceCities[i + 1] - spaceCities[i]) / 2)
		if d > maxInBet:
			maxInBet = d
	maxBefore = spaceCities[0] - 0
	maxAfter = n - 1 - spaceCities[-1]
	print(max(maxInBet, maxBefore, maxAfter))
main()


import sys
import math
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c.sort()
maxDisBetwCities = 0
for i in range(m - 1):
	d = c[i + 1] - c[i]
	if d > maxDisBetwCities:
		maxDisBetwCities = d
maxDisBetwCities = int(math.ceil((maxDisBetwCities - 1) / 2))
d = c[0]
if d > maxDisBetwCities:
	maxDisBetwCities = d
d = n - 1 - c[-1]
if d > maxDisBetwCities:
	maxDisBetwCities = d
print(maxDisBetwCities)


(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c.sort()
d = [c[0], n - 1 - c[-1]]
for i in range(len(c) - 1):
	d.append((c[i + 1] - c[i]) // 2)
print(max(d))


import sys
import math
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
stations = sorted(c)
distance = stations[0]
distance = max(distance, n - stations[-1] - 1)
for i in range(1, len(stations)):
	distance = max(distance, math.floor((stations[i] - stations[i - 1]) / 2))
print(distance)


import math

def f(i):
	return round((i - i % 2) / 2)
inp = list(map(int, input().split()))
n = inp[0]
m = inp[1]
A = list(map(int, input().split()))
A.sort()
ma = max(A[0], n - 1 - A[m - 1])
for i in range(0, m - 1):
	d = f(A[i + 1] - A[i])
	if d > ma:
		ma = d
print(ma)


import sys
import itertools

def pairwise(iterable):
	(a, b) = itertools.tee(iterable)
	next(b, None)
	return zip(a, b)
(n, m) = map(int, input().strip().split(' '))
c = sorted(map(int, input().strip().split(' ')))
maxDist = max(c[0], n - 1 - c[-1])
for (bot, top) in pairwise(c):
	maxDist = max(maxDist, (top - bot) // 2)
print(maxDist)


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
r = [n for _ in range(n)]
l = [n for _ in range(n)]
for i in c:
	r[i] = 0
	l[i] = 0
for i in range(1, n):
	if r[i] > 0:
		r[i] = r[i - 1] + 1
for i in range(n - 2, -1, -1):
	if l[i] > 0:
		l[i] = l[i + 1] + 1
max_dis = max([min(r[i], l[i]) for i in range(n)])
print(max_dis)


import sys
(n, m) = input().strip().split(' ')
(n, m) = (int(n), int(m))
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c.sort()
dists = []
dists.append(c[0])
dists.append(n - 1 - c[-1])
for (i, j) in zip(c[:-1], c[1:]):
	dists.append((j - i) // 2)
print(max(dists))


import sys
import math
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c.sort()
diffs = [0] * (len(c) + 1)
for i in range(1, len(c)):
	diffs[i] = math.floor((c[i] - c[i - 1]) / 2)
diffs[0] = c[0]
diffs[-1] = n - 1 - c[-1]
print(max(diffs))


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c.sort()
if len(c) == 1:
	dist = max(c[0], n - c[0] - 1)
else:
	dist = int(max((abs(x - y) for (x, y) in zip(c[1:], c[:-1]))) / 2)
	if c[0] > dist:
		dist = c[0]
	if n - c[-1] > dist:
		dist = n - c[-1] - 1
print(dist)


import math

def max_dist(cities, n, m):
	left = -1
	right = -1
	max_dist = 0
	left_dist = 0
	right_dist = 0
	for i in range(n):
		if cities[i] == 1:
			if left == -1:
				left = i
				left_dist = left
			else:
				right = i
				dist = right - left - 1
				if dist > max_dist:
					max_dist = dist
				left = right
				right = -1
	if right == -1:
		right_dist = n - left - 1
	return max(math.ceil(max_dist / 2), left_dist, right_dist)
(n, m) = map(int, input().split())
c = list(map(int, input().split()))
cities = [0 for i in range(n)]
for i in range(m):
	cities[c[i]] = 1
print(max_dist(cities, n, m))


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c = sorted(c)
max_travel = max(c[0], n - 1 - c[-1])
for i in range(len(c) - 1):
	two_cities_dist = c[i + 1] - c[i]
	two_cities_max_travel = two_cities_dist // 2
	max_travel = max(max_travel, two_cities_max_travel)
print(max_travel)


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
d = [-1] + sorted(c) + [n]
e = []
for i in range(m + 1):
	e += [d[i + 1] - d[i]]
f = []
if len(e) > 2:
	f = [max(e[1:-1]) // 2]
if c[0] != 0:
	f += [e[0] - 1]
if c[-1] != n - 1:
	f += [e[-1] - 1]
if f == []:
	print(0)
else:
	print(max(f))


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
s = sorted(c)
max_dist = 0
for i in range(0, len(s) - 1):
	max_dist = max(max_dist, abs(s[i] - s[i + 1]))
max_op = max_dist // 2
if n - s[-1] - 1 > max_op:
	max_op = n - s[-1] - 1
if s[0] > max_op:
	max_op = s[0]
if n == m:
	print(0)
else:
	print(max_op)


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
a = [0] * n
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c.sort()
f = 0
d = max(c[0], n - c[len(c) - 1] - 1)
for i in range(len(c) - 1):
	d_temp = c[i + 1] - c[i]
	if d_temp / 2 > d:
		f = 1
		d = d_temp / 2
print(int(d))


import sys

def main():
	(n, m) = input().strip().split(' ')
	(n, m) = [int(n), int(m)]
	c = [int(c_temp) for c_temp in input().strip().split(' ')]
	c.sort()
	if n == m:
		print(0)
		return None
	if n == m + 1:
		print(1)
		return None
	maxDist = 1
	for i in range(len(c) - 1):
		c1 = c[i]
		c2 = c[i + 1]
		if c2 - c1 - 1 > maxDist:
			maxDist = c2 - c1 - 1
	if maxDist % 2 == 0:
		maxDist = maxDist // 2
	else:
		maxDist = maxDist // 2 + 1
	firstLast = False
	if c[0] > maxDist:
		maxDist = c[0]
		firstLast = True
	if n - 1 - c[-1] > maxDist:
		maxDist = n - 1 - c[-1]
		firstLast = True
	if firstLast:
		print(maxDist)
		return None
	print(maxDist)
main()


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c.sort()
max_dist = 0
if c[0] != 0:
	max_dist = c[0]
if c[-1] != n - 1:
	max_dist = max(n - 1 - c[-1], max_dist)
for i in range(1, len(c)):
	dist = (c[i] - c[i - 1]) // 2
	if dist > max_dist:
		max_dist = dist
print(max_dist)


import sys
(n, m) = input().strip().split(' ')
c = sorted([int(c_temp) for c_temp in input().strip().split(' ')])
if len(c) == 1:
	print(max([c[0], int(n) - c[0] - 1]))
else:
	d = max([abs(c[i] - c[i + 1]) // 2 for i in range(len(c) - 1)])
	print(max(d, c[0], int(n) - c[len(c) - 1] - 1))


import sys

def binary_search(array, t):
	l = 0
	r = len(array) - 1
	while l < r:
		m = (l + r) // 2
		if array[m] < t:
			l = m + 1
		else:
			r = m
	return l
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c.sort()
ans = 0
for i in range(n):
	k = binary_search(c, i)
	if k == len(c) - 1 and c[k] < i:
		dist = i - c[-1]
		ans = max(ans, dist)
	if k == 0:
		dist = c[0] - i
		ans = max(ans, dist)
	else:
		dist = min(c[k] - i, i - c[k - 1])
		ans = max(ans, dist)
print(ans)


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c.sort()
maxim = max(c[0], n - 1 - c[-1])
for i in range(len(c) - 1):
	if abs(c[i] - c[i + 1]) // 2 > maxim:
		maxim = abs(c[i] - c[i + 1]) // 2
print(maxim)


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c.sort()
diffs = [(c[i + 1] - c[i]) // 2 for i in range(len(c) - 1)]
current_max = 0
if diffs:
	current_max = max(max(diffs), current_max)
current_max = max(current_max, c[0])
current_max = max(current_max, n - 1 - c[-1])
print(current_max)


def main():
	(n, m) = input().strip().split(' ')
	(n, m) = [int(n), int(m)]
	c = [int(c_temp) for c_temp in input().strip().split(' ')]
	c.sort()
	ans = -1
	for i in range(m - 1):
		ans = max(ans, (c[i + 1] - c[i]) // 2)
	ans = max(ans, c[0] - 0)
	ans = max(ans, n - 1 - c[m - 1])
	print(ans)
main()


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c = sorted(c)
maxs = c[0]
for i in range(1, len(c)):
	x = c[i] - c[i - 1] >> 1
	if maxs < x:
		maxs = x
if n - c[len(c) - 1] - 1 > maxs:
	maxs = n - c[len(c) - 1] - 1
print(maxs)


DEBUG = False
(n, m) = input().strip().split(' ')
(num_cities, num_stations) = [int(n), int(m)]
distances = []
stations = [int(c_temp) for c_temp in input().strip().split(' ')]
stations.sort()
if DEBUG:
	print('{} cities, stations at{}'.format(num_cities, stations))
previous_station = None
next_station = 0
for city in range(num_cities):
	if DEBUG:
		print('city:{}, prev:{}, next:{}'.format(city, previous_station, next_station))
	if next_station is not None and city == stations[next_station]:
		if DEBUG:
			print('city has station')
		distances.append(0)
		previous_station = next_station
		next_station += 1
		if next_station == len(stations):
			next_station = None
	else:
		if previous_station is None:
			previous_distance = num_cities
		else:
			previous_distance = city - stations[previous_station]
		if next_station is None:
			next_distance = num_cities
		else:
			next_distance = stations[next_station] - city
		if DEBUG:
			print('prev dist: {}, next dist: {}'.format(previous_distance, next_distance))
		distances.append(min(previous_distance, next_distance))
		if DEBUG:
			print('distance:', distances[-1])
if DEBUG:
	print('distances', distances)
print(max(distances))


(n, m) = map(int, input().split())
c = sorted(map(int, input().split()))
print(max([c[0], n - 1 - c[-1]] + [(c[i + 1] - c[i]) // 2 for i in range(m - 1)]))


import sys
import math
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c.sort()
if n == m or n == m - 1:
	print(n - m)
else:
	arr = []
	for j in range(m + 1):
		if j == 0:
			arr.append(c[0])
		elif j == m:
			arr.append(n - 1 - c[m - 1])
		else:
			arr.append(math.floor((c[j] - c[j - 1]) / 2))
	print(max(arr))


(n, m) = list([int(x) for x in input().split()])
c = sorted([int(x) for x in input().split()])
max_d = 0
for x in range(1, len(c)):
	d = c[x] - c[x - 1]
	if max_d < d:
		max_d = d
max_d //= 2
if max_d < c[0]:
	max_d = c[0]
last = n - c[-1] - 1
if max_d < last:
	max_d = last
print(max_d)


import sys

def Solution():
	(n, m) = input().strip().split(' ')
	(n, m) = [int(n), int(m)]
	if n == m:
		print(0)
		return
	if n == m - 1:
		print(1)
		return
	c = [int(c_temp) for c_temp in input().strip().split(' ')]
	c = sorted(c)
	if len(c) == 1:
		print(max(c[0], n - c[0] - 1))
		return
	maxDist = max(c[0], n - c[-1] - 1)
	for (i, station) in enumerate(c[1:]):
		dist = station - c[i + 1 - 1] - 1
		if dist == 0:
			continue
		if dist % 2 == 0:
			minDist = dist / 2
		else:
			minDist = (dist - 1) / 2 + 1
		if minDist > maxDist:
			maxDist = minDist
	print(int(maxDist))
Solution()


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
first = 0
last = n - 1
distance = 0
c.sort()
for i in range(len(c) - 1):
	if c[i + 1] - c[i] > distance:
		distance = c[i + 1] - c[i]
answer = distance // 2
if c[0] - first > answer:
	answer = c[0] - first
if last - c[m - 1] > answer:
	answer = last - c[m - 1]
print(answer)


import sys
from bisect import bisect_right
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = sorted((int(c_temp) for c_temp in input().strip().split(' ')))
cities = list(range(n))
max_dist = float('-inf')
for city in cities:
	i = bisect_right(c, city)
	nearest = float('inf')
	if i > 0:
		nearest = abs(c[i - 1] - city)
	if i < len(c) and abs(c[i] - city) < nearest:
		nearest = abs(c[i] - city)
	max_dist = max(max_dist, nearest)
print(max_dist)


from math import floor
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = sorted([int(c_temp) for c_temp in input().strip().split(' ')])
arr = []
if c[0] != 0:
	arr.append(c[0])
for (i, j) in zip(c, c[1:]):
	arr.append(floor((j - i) / 2))
if c[-1] != n - 1:
	arr.append(n - 1 - c[-1])
if len(arr) > 0:
	print(max(arr))
else:
	print(0)


import sys
(n, m) = [int(x) for x in input().strip().split(' ')]
c = [int(x) for x in input().strip().split(' ')]
c.sort()
dist = 0
if c[0]:
	dist = c[0]
if c[-1] != n - 1:
	dist = max(dist, n - c[-1] - 1)
for x in range(len(c) - 1):
	dist = max(dist, (c[x + 1] - c[x]) // 2)
print(dist)


import sys
(n, m) = map(int, input().strip().split(' '))
stations = sorted(list(map(int, input().strip().split(' '))))
pointer = 0
maxofmin = 0
for i in range(0, n):
	if i <= stations[pointer]:
		val = stations[pointer] - i
	elif pointer < m - 1:
		val1 = abs(stations[pointer] - i)
		val2 = abs(stations[pointer + 1] - i)
		if val1 > val2:
			pointer = pointer + 1
			val = val2
		else:
			val = val1
	else:
		val = abs(i - stations[pointer])
	maxofmin = max(maxofmin, val)
print(maxofmin)


import sys
import math
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
d = set(c)
cities = []
for i in range(n):
	if i in d:
		cities.append(1)
	else:
		cities.append(0)
start = 0
end = 0
consec = 0
max = 0
for i in range(n):
	if cities[i] == 0 and i != n - 1:
		consec += 1
	else:
		end = cities[i]
		if end == 1 and start == 1:
			consec = math.ceil(consec / float(2))
		elif end == 0:
			consec += 1
		if consec > max:
			max = consec
		start = cities[i]
		consec = 0
print(max)


import sys
import math
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
d = set(c)
cities = []
for i in range(n):
	if i in d:
		cities.append(1)
	else:
		cities.append(0)
start = 0
end = 0
consec = 0
max = 0
for i in range(n):
	if cities[i] == 0 and i != n - 1:
		consec += 1
	else:
		end = cities[i]
		if end == 1 and start == 1:
			consec = math.ceil(consec / float(2))
		elif end == 0:
			consec += 1
		if consec > max:
			max = consec
		start = cities[i]
		consec = 0
print(max)


import sys

def flatlandSpaceStation(input):
	totalNumberOfCities = input[0][0]
	numberOfCitiesWithSS = input[0][1]
	citiesWithSS = set(input[1])
	maxDistance = 0
	values = {}
	for cityNumber in range(totalNumberOfCities):
		values[cityNumber] = sys.maxsize
	for cityNumber in range(totalNumberOfCities):
		if cityNumber in citiesWithSS:
			values[cityNumber] = 0
			for cityNumber2 in range(cityNumber - 1, -1, -1):
				if cityNumber2 in citiesWithSS:
					break
				values[cityNumber2] = min(values[cityNumber2], abs(cityNumber - cityNumber2))
			for cityNumber2 in range(cityNumber + 1, totalNumberOfCities, 1):
				if cityNumber2 in citiesWithSS:
					break
				values[cityNumber2] = min(values[cityNumber2], abs(cityNumber - cityNumber2))
	return max(values.values())
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
testcase = []
testcase.append([int(n), int(m)])
testcase.append(c)
res = flatlandSpaceStation(testcase)
print(res)


from math import ceil
(cities, stations) = [int(x) for x in input().strip().split(' ')]
station_cities = [int(c_temp) for c_temp in input().strip().split(' ')]

def find_max_dist(city_list):
	dist_list = []
	city_list.sort()
	for i in range(len(city_list)):
		try:
			dist_list.append(abs(city_list[i] - city_list[i + 1]))
		except IndexError:
			pass
	first_city = abs(0 - city_list[0])
	last_city = abs(cities - (city_list[-1] + 1))
	return max(first_city, last_city, ceil(max(dist_list, default=0) // 2), 0)
print(find_max_dist(station_cities))


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
if n == m:
	print(0)
	sys.exit(0)
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c.sort()
values = []
for i in range(1, len(c)):
	values.append((c[i] - c[i - 1]) // 2)
if values:
	result = max(values)
else:
	result = -1
result = max([result, n - c[-1] - 1, c[0]])
print(result)


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c.sort()
dists = [c[0], n - 1 - c[-1]]
for i in range(1, m):
	dists += [(c[i] - c[i - 1]) // 2]
print(max(dists))


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = sorted([int(c_temp) for c_temp in input().strip().split(' ')])
pos = 0
dist = []
for i in range(n):
	tc = c[pos:pos + 2]
	y = map(lambda x: abs(x - i), tc)
	dist.append(min(y))
	if len(tc) == 2 and tc[0] <= i and (i <= tc[1]):
		if i >= int((tc[1] + tc[0]) / 2):
			pos = pos + 1
print(dist, file=sys.stderr)
print(max(dist))


def ceildiv(a, b):
	return -(-a // b)
(N, M) = [int(x) for x in input().strip().split(' ')]
C = [int(x) for x in input().strip().split(' ')]
A = [0] * N
for c in C:
	A[c] = 1
current = 0
largest = 0
half = False
for a in A:
	if a == 0:
		current += 1
	else:
		if half:
			current = -(-current // 2)
		largest = max(current, largest)
		current = 0
		half = True
largest = max(current, largest)
print(largest)


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
if n == m:
	print(0)
else:
	c = sorted(c)
	max_dist = c[0]
	for i in range(m - 1):
		current_dist = (c[i + 1] - c[i]) // 2
		max_dist = max(max_dist, current_dist)
	print(max(max_dist, n - 1 - c[m - 1]))


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c.sort()
if len(c) == 1:
	distances = []
	distances.append(c[0])
	distances.append(n - c[len(c) - 1] - 1)
else:
	distances = [(c[i + 1] - c[i]) // 2 for i in range(len(c) - 1)]
	distances.append(c[0])
	distances.append(n - c[len(c) - 1] - 1)
print(max(distances))


import sys
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c.sort()
max_distance = max(c[0], n - 1 - c[-1])
for station in range(1, m):
	max_distance = max((c[station] - c[station - 1]) // 2, max_distance)
print(max_distance)