Watson gives Sherlock an array of integers.  Given the endpoints of an integer range, for all $M$ in that inclusive range, determine the minimum( abs(arr[i]-M) for all $1\leq i\leq|arr|$) ).  Once that has been determined for all integers in the range, return the $M$ which generated the maximum of those values.  If there are multiple $M$'s that result in that value, return the lowest one.  

For example, your array $arr=[3,5,7,9]$ and your range is from $p=6$ to $q=8$ inclusive.

M	|arr[1]-M|	|arr[2]-M|	|arr[3]-M|	|arr[4]-M|	Min
6	   3		   1		   1		   3		 1
7	   4		   2		   0		   2		 0
8	   5		   3		   1		   1		 1

We look at the Min column and see the maximum of those three values is $1$.  Two $M$'s result in that answer so we choose the lower value, $6$.

Function Description  

Complete the sherlockAndMinimax function in the editor below.  It should return an integer as described.  

sherlockAndMinimax has the following parameters: 

- arr: an array of integers 

- p: an integer that represents the lowest value of the range for $M$ 

- q: an integer that represents the highest value of the range for $M$  

Input Format

The first line contains an integer $n$, the number of elements in $arr$. 

The next line contains $n$ space-separated integers $i$. 

The third line contains two space-separated integers $p$ and $q$, the inclusive endpoints for the range of $M$.       

Constraints

$1\leq n\leq10^2$ 

$1\leq ar r[i]\leq10^9$ 

$1\leq p\leq q\leq10^9$  

Output Format

Print the value of $M$ on a line.

Sample Input
3
5 8 14
4 9

Sample Output
4

Explanation

$arr=[5,8,14],range=[4-9]$

M	|arr[1]-M|	|arr[2]-M|	|arr[3]-M|	Min
4	   1		   4		   10		 1
5	   0		   3		    9		 0
6	   1		   2		    8		 1
7	   2		   1		    7		 1
8	   3		   0		    6		 0
9	   4		   1		    5		 1

For $M=4,6,7$, or $9$, the result is $1$. Since we have to output the smallest of the multiple solutions, we print $4$.

Difficulty: MEDIUM_HARD
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
N = int(input())
A = [int(c) for c in input().split()[:N]]
(P, Q) = [int(c) for c in input().split()[:2]]
a = sorted(A)
max_point = P
max_distance = min((abs(i - P) for i in a))
for i in range(len(a) - 1):
	if a[i] > Q or a[i + 1] < P:
		continue
	m = int((a[i] + a[i + 1]) / 2)
	if m < P:
		point = P
		distance = a[i + 1] - P
	elif m > Q:
		point = Q
		distance = Q - a[i]
	else:
		point = m
		distance = m - a[i]
	if distance > max_distance:
		max_point = point
		max_distance = distance
point = Q
distance = min((abs(i - Q) for i in a))
if distance > max_distance:
	max_point = point
	max_distance = distance
print(max_point)


N = int(input())
A = [int(_) for _ in input().split(' ')]
(P, Q) = [int(_) for _ in input().split(' ')]
A.sort()
(Pm, Qm) = (A[-1] - A[0], A[-1] - A[0])
for a in A:
	if abs(a - P) < Pm:
		Pm = abs(a - P)
	if abs(a - Q) < Qm:
		Qm = abs(a - Q)
M = (Pm, P)
for i in range(len(A) - 1):
	(m, d) = ((A[i] + A[i + 1]) // 2, (A[i + 1] - A[i]) // 2)
	if d > M[0] and m >= P and (m <= Q):
		M = (d, m)
if Qm > M[0]:
	M = (Qm, Q)
print(M[1])


def intersects(a, b, p, q):
	return b >= p and a <= q
array_size = int(input())
array = list(map(int, input().split(' ')))
(p, q) = map(int, input().split(' '))
array.sort()
diff_max = -1
m_max = -1
if array[0] > p:
	if array[0] - p > diff_max:
		diff_max = array[0] - p
		m_max = p
for (x, y) in zip(array, array[1:]):
	if intersects(x, y, p, q):
		mid = x + (y - x) // 2
		if mid > q:
			mid = q
		if mid < p:
			mid = p
		diff = min(y - mid, mid - x)
		if diff > diff_max:
			diff_max = diff
			m_max = mid
if array[-1] < q:
	if q - array[-1] > diff_max:
		diff_max = q - array[-1]
		m_max = q
print(m_max)


def test(v):
	minimum = 1000000000
	for x in arr:
		minimum = min(minimum, abs(x - v))
	return minimum
n = int(input())
arr = list(map(int, input().split()))
(p, q) = map(int, input().split())
arr.sort()
res = 0
resi = p
tmp = test(p)
if tmp > res:
	res = tmp
	resi = p
for i in range(len(arr) - 1):
	n = int((arr[i] + arr[i + 1]) / 2)
	if n < p or n > q:
		continue
	tmp = test(n)
	if tmp > res:
		res = tmp
		resi = n
tmp = test(q)
if tmp > res:
	res = tmp
	resi = q
print(resi)


import sys
N = int(input())
l = list(map(int, input().split()))
(P, Q) = map(int, input().split())
l.sort()
maxMinHalf = 0
Mmax = sys.maxsize
for i in range(N - 1):
	m = (l[i] + l[i + 1]) // 2
	minHalf = abs(l[i] - m)
	if minHalf > maxMinHalf or (minHalf == maxMinHalf and m < Mmax):
		if P <= m and m <= Q:
			maxMinHalf = minHalf
			Mmax = m
minHalf = min([abs(P - l[i]) for i in range(N)])
if minHalf > maxMinHalf or (minHalf == maxMinHalf and P < Mmax):
	maxMinHalf = minHalf
	Mmax = P
minHalf = min([abs(Q - l[i]) for i in range(N)])
if minHalf > maxMinHalf or (minHalf == maxMinHalf and Q < Mmax):
	maxMinHalf = minHalf
	Mmax = Q
print(Mmax)


def solve(numbers, P, Q):
	numbers = sorted(numbers)
	(best, minimax) = (P, -1)

	def check(candidate, dist):
		if dist > minimax:
			return (candidate, dist)
		return (best, minimax)
	if P < numbers[0]:
		(best, minimax) = check(P, numbers[0] - P)
	if Q > numbers[-1]:
		(best, minimax) = check(Q, Q - numbers[-1])
	(start, end) = (max(P, numbers[0]), min(Q, numbers[-1]))
	for (left, right) in zip(numbers, numbers[1:]):
		if start > end:
			break
		if left <= start <= right:
			median = (left + right) // 2
			if median < end:
				(best, minimax) = check(median, median - left)
			else:
				(best, minimax) = check(end, end - left)
			start = right
	return best

def main():
	N = int(input())
	numbers = list(map(int, input().split()))
	assert len(numbers) == N
	(P, Q) = map(int, input().split(maxsplit=1))
	print(solve(numbers, P, Q))
main()


from bisect import bisect_left, bisect_right

def minimum(l, x):
	mn = float('inf')
	for i in range(len(l)):
		mn = min(mn, abs(l[i] - x))
	return mn

def eval(l, i, best):
	test = minimum(l, i)
	if test > best[1]:
		return (i, test)
	else:
		return best
n = int(input())
l = [int(x) for x in input().strip().split()]
l.sort()
assert n == len(l)
(p, q) = [int(x) for x in input().strip().split()]
best = (None, float('-inf'))
best = eval(l, p, best)
i = bisect_left(l, p) - 1
j = bisect_right(l, q)
j = min(j, n - 1)
for x in range(i, j):
	m = (l[x] + l[x + 1]) // 2
	if m < p or m > q:
		continue
	best = eval(l, m, best)
best = eval(l, q, best)
print(best[0])


def sherlock(arr, P, Q):
	arr = list(arr)
	arr.sort()
	(best_pos, best_dist) = (None, None)
	if P < arr[0]:
		dist = arr[0] - P
		if best_dist is None or best_dist < dist:
			(best_pos, best_dist) = (P, dist)
	for i in range(len(arr) - 1):
		(x, y) = (arr[i], arr[i + 1])
		midpoint = (x + y) // 2
		if x <= P and P < y:
			dist = min(P - x, y - P)
			if best_dist is None or best_dist < dist:
				(best_pos, best_dist) = (P, dist)
		if P <= midpoint and midpoint < Q:
			dist = (y - x) // 2
			if best_dist is None or best_dist < dist:
				(best_pos, best_dist) = (midpoint, dist)
		if x <= Q and Q < y:
			dist = min(Q - x, y - Q)
			if best_dist is None or best_dist < dist:
				(best_pos, best_dist) = (Q, dist)
	if arr[len(arr) - 1] <= Q:
		dist = Q - arr[len(arr) - 1]
		if best_dist is None or best_dist < dist:
			(best_pos, best_dist) = (Q, dist)
	return best_pos
N = int(input().strip())
arr = tuple((int(n) for n in input().strip().split()))
(P, Q) = (int(n) for n in input().strip().split())
M = sherlock(arr, P, Q)
print(M)


def rl(T=str):
	return list(map(T, input().split()))
(n,) = rl(int)
v = rl(int)
(p, q) = rl(int)

def go(a, b, p, q):

	def get(s):
		return min(s - a, b - s)
	if q < a or p > b:
		return (None, None)
	p = max(p, a)
	q = min(q, b)
	m = (a + b) // 2
	if p >= m + 1:
		return (p, get(p))
	if q <= m:
		return (q, get(q))
	return (m, get(m))
v.append(-10 ** 10)
v.append(10 ** 10)
v.sort()
n = len(v)
best_c = None
best_d = None
for i in range(n - 1):
	(c, d) = go(v[i], v[i + 1], p, q)
	if c is not None and (best_d is None or d > best_d):
		(best_c, best_d) = (c, d)
print(best_c)


input()
nums = sorted(list(map(int, input().split(' '))))
(P, Q) = list(map(int, input().split(' ')))

def find_mini_max(nums, P, Q):
	nums = sorted(nums)
	if P == Q:
		return P
	if Q <= nums[0]:
		return P
	if P >= nums[-1]:
		return Q
	if P <= nums[0]:
		prev_diff = nums[0] - P
		num = P
		start = 1
	else:
		start = 0
		while start < len(nums) and nums[start] <= P:
			start += 1
		diff1 = nums[start] - P
		diff2 = P - nums[start - 1]
		prev_diff = min(diff1, diff2)
		num = P
	for i in range(start, len(nums)):
		mid = (nums[i - 1] + nums[i]) // 2
		if nums[i - 1] <= Q and Q <= nums[i]:
			mid = min(mid, Q)
		if mid - nums[i - 1] > prev_diff:
			prev_diff = mid - nums[i - 1]
			num = mid
		if nums[i - 1] <= Q and Q <= nums[i]:
			break
	if Q >= nums[-1]:
		if Q - nums[-1] > prev_diff:
			prev_diff = Q - nums[-1]
			num = Q
	return num
print(find_mini_max(nums, P, Q))


n = int(input())
a = sorted(list(map(int, input().split())))
(p, q) = [int(e) for e in input().split()]
v1 = min((abs(e - p) for e in a))
v2 = min((abs(e - q) for e in a))
md = 0
mv = 0
for (i, e) in enumerate(a[:-1]):
	if p <= (a[i + 1] + e) / 2 <= q and a[i + 1] - e > md:
		md = a[i + 1] - e
		if (a[i + 1] + e) % 2 == 0 or (a[i + 1] + e) // 2 > p:
			mv = (a[i + 1] + e) // 2
		else:
			mv = (a[i + 1] + e) // 2 + 1
v3 = min((abs(e - mv) for e in a))
mtv = max(v1, v2, v3)
if mtv == v1:
	print(p)
elif mtv == v3:
	print(mv)
else:
	print(q)


import bisect
input()
a = sorted(map(int, input().split()))
n = len(a)
(p, q) = map(int, input().split())
b = [(a[i + 1] + a[i]) // 2 for i in range(n - 1)]
pidx = bisect.bisect(b, p)
qidx = bisect.bisect(b, q)

def get_val(i):
	return b[i] - a[i] if i > -1 else 0
pscore = abs(p - a[pidx])
qscore = abs(q - a[qidx])
betidx = -1 if pidx == qidx else max(range(pidx, qidx), key=get_val)
best = max(pscore, qscore, get_val(betidx))
if best == pscore:
	print(p)
elif best == get_val(betidx):
	print(b[betidx])
else:
	print(q)


input()
data = map(int, input().split())
(p, q) = map(int, input().split())
data = list(map(lambda x: x - p, sorted(data)))
index = next((i for (i, x) in enumerate(data) if x >= 0), None)
min_value = min(data[index], abs(data[index - 1])) if index is not None else abs(data[-1])
d_min = p
if index is not None:
	if index > 0:
		diff = (data[index] + data[index - 1]) // 2
		curr_min = abs(data[index - 1]) + min(diff, q - p)
		if curr_min > min_value:
			min_value = curr_min
			d_min = p + curr_min - abs(data[index - 1])
	while index < len(data) and data[index] <= q - p:
		if index + 1 == len(data):
			curr_min = abs(data[index] - (q - p))
		else:
			diff = (data[index + 1] - data[index]) // 2
			curr_min = min(diff, q - p - data[index])
		if curr_min > min_value:
			min_value = curr_min
			d_min = q if index + 1 == len(data) else data[index] + p + curr_min
		index += 1
print(d_min)


n = int(input())
a = sorted([int(x) for x in input().split()])
(p, q) = (int(x) for x in input().split())

def maxd(m):
	d = 10 ** 9
	for ai in a:
		if abs(ai - m) < d:
			d = abs(ai - m)
	return d
val = p
vald = maxd(p)
for i in range(n - 1):
	m = (a[i] + a[i + 1]) // 2
	d = m - a[i]
	if m > p and m < q and (d > vald):
		val = m
		vald = d
if maxd(q) > vald:
	val = q
print(val)


N = int(input())
A = [int(x) for x in input().split()]
A = [0] + sorted(A) + [10 ** 10 + 1]
(P, Q) = [int(x) for x in input().split()]
if P > Q:
	(P, Q) = (Q, P)
best = 0
best_m = 0
for i in range(N + 1):
	low = A[i]
	high = A[i + 1]
	if P > high or Q < low:
		continue
	mid = (high + low) // 2
	if mid < P or i == 0:
		mid = P
	elif mid > Q or i == N:
		mid = Q
	if i == 0:
		attempt = high - mid
	elif i == N:
		attempt = mid - low
	else:
		attempt = min(mid - low, high - mid)
	if attempt > best:
		best = attempt
		best_m = mid
print(best_m)


from bisect import bisect_left, bisect_right

def getint():
	return int(input())

def getintlist():
	return [int(i) for i in input().split()]
N = getint()
l = sorted(getintlist())
(P, Q) = getintlist()
gendis = lambda x, y: ((y - x) // 2, (y + x) // 2)
dis_val = [gendis(l[i], l[i + 1]) for i in range(N - 1)]
dis_val = [p for p in dis_val if P <= p[1] <= Q]
dis_val = [(min((abs(t - P) for t in l)), P)] + dis_val
dis_val = dis_val + [(min((abs(t - Q) for t in l)), Q)]
(dis, v) = max(dis_val, key=lambda p: p[0])
print(v)


n = int(input())
a = list(map(int, input().split()))
(p, q) = [int(i) for i in input().split()]
a.sort()
for i in range(n):
	if a[i] > p and i == 0:
		start = 0
		max_dif_ind = p
		max_dif = a[i] - p
	elif a[i - 1] <= p <= a[i]:
		start = i - 1
		max_dif_ind = p
		max_dif = min(p - a[i], a[i + 1] - p)
	if a[i] < q and i == n - 1:
		finish = n - 1
		dif = q - a[i]
		if dif > max_dif:
			max_dif = dif
			max_dif_ind = q
		break
	elif a[i] <= q <= a[i + 1]:
		finish = i + 1
		dif = min(q - a[i], a[i + 1] - q)
		if dif > max_dif:
			max_dif = dif
			max_dif_ind = q
		break
for i in range(start, finish):
	dif = (a[i + 1] - a[i]) // 2
	if p < a[i] + dif <= q:
		if dif > max_dif:
			max_dif = dif
			max_dif_ind = a[i] + dif
dif = min(q - a[finish - 1], a[finish] - q)
print(max_dif_ind)


def find_border(arr, P, Q):
	left = -1
	right = -1
	for i in range(len(arr) - 1):
		if arr[i] < P and arr[i + 1] >= P:
			left = i
		if arr[i] < Q and arr[i + 1] >= Q:
			right = i
	return (left, right)

def inrange(num, left, right):
	if num >= left and num <= right:
		return True
	else:
		return False
T = int(input().strip())
arr = [int(i) for i in input().strip().split()]
(P, Q) = [int(i) for i in input().strip().split()]
arr.sort()
(left, right) = find_border(arr, P, Q)
result = P
minus = 0
if left == -1:
	minus = abs(arr[0] - P)
	result = P
else:
	minus = min(P - arr[left], arr[left + 1] - P)
	result = P
if left == -1:
	ileft = 0
else:
	ileft = left
if right == -1:
	iright = len(arr) - 1
else:
	iright = right + 1
for i in range(ileft, iright):
	tmp = int((arr[i + 1] - arr[i]) / 2)
	if tmp > minus and inrange(arr[i] + tmp, P, Q):
		minus = tmp
		result = arr[i] + tmp
if right == -1 and minus < abs(Q - arr[right]):
	minus = abs(Q - arr[right])
	result = Q
elif minus < min(Q - arr[right], arr[right + 1] - Q):
	minus = min(Q - arr[right], arr[right + 1] - Q)
	result = Q
print(result)


import sys

def minimax(a, p, q):
	a.sort()
	best_diff = best_mid = 0
	for i in range(len(a) - 1):
		diff = a[i + 1] - a[i]
		mid = a[i] + int(diff / 2)
		if p <= mid <= q and diff > best_diff:
			best_diff = diff
			best_mid = a[i] + int(diff / 2)
	best_p = sys.maxsize
	best_q = sys.maxsize
	for v in a:
		diff_p = abs(v - p)
		diff_q = abs(v - q)
		if diff_p < best_p:
			best_p = diff_p
		if diff_q < best_q:
			best_q = diff_q
	best = best_mid
	if int(best_diff / 2) <= best_p:
		best = p
	if int(best_diff / 2) <= best_q and best_p < best_q:
		best = q
	return best
input()
a = list(map(int, input().strip().split()))
(p, q) = map(int, input().strip().split())
print(minimax(a, p, q))


length = int(input())
array = sorted([int(i) for i in input().split()])
(p, q) = [int(i) for i in input().split()]
startindex = 0
stopindex = length - 1
while startindex < stopindex and array[startindex] < p:
	startindex += 1
while stopindex > 0 and array[stopindex] > q:
	stopindex -= 1
if startindex == 0:
	gap = abs(array[startindex] - p)
	gapindex = p - gap
	assert gap + gapindex == p
elif startindex > 0:
	gaptemp = int((array[startindex] - array[startindex - 1]) / 2)
	gapindex = array[startindex - 1]
	if gaptemp + gapindex >= p and gaptemp + gapindex <= q:
		gap = gaptemp
	else:
		gaptemp = min([abs(array[startindex] - p), abs(array[startindex - 1] - p)])
		gap = gaptemp
		gapindex = abs(p - gap)
for i in range(startindex, stopindex):
	gaptemp = int((array[i + 1] - array[i]) / 2)
	if gaptemp > gap and gaptemp + array[i] >= p and (gaptemp + array[i] <= q):
		gapindex = array[i]
		gap = gaptemp
if stopindex == length - 1:
	gaptemp = abs(q - array[stopindex])
	if gaptemp > gap:
		gap = gaptemp
		gapindex = abs(q - gaptemp)
		assert gap + gapindex == q
elif stopindex < length - 1:
	gaptemp = int((array[stopindex + 1] - array[stopindex]) / 2)
	if gaptemp > gap and gaptemp + array[stopindex] >= p and (array[stopindex] + gaptemp <= q):
		gapindex = array[stopindex]
		gap = gaptemp
	gaptemp = min([abs(q - array[stopindex]), abs(array[stopindex + 1] - q)])
	if gaptemp > gap:
		gap = gaptemp
		gapindex = abs(q - gaptemp)
		assert gap + gapindex == q
print(gap + gapindex)


def get_testcase():
	_ = int(input())
	A = list(map(int, input().split()))
	(P, Q) = map(int, input().split())
	return (A, P, Q)

def sherlock_and_minimax_1(A, P, Q):
	result = (-1, -1)
	for M in range(P, Q + 1):
		minimum = min([A_i - M if A_i > M else M - A_i for A_i in A])
		if minimum > result[0]:
			result = (minimum, M)
	return result[1]

def sherlock_and_minimax_2(A, P, Q):
	A = list(A)
	A.sort()
	if Q <= A[0]:
		return Q
	if P >= A[-1]:
		return P
	result = (-1, -1)
	if P <= A[0]:
		result = (A[0] - P, P)
	if A[-1] <= Q:
		minimum = Q - A[-1]
		if minimum > result[0]:
			result = (minimum, Q)
	for i in range(len(A) - 1):
		M = int((A[i] + A[i + 1]) / 2)
		if P <= M and M <= Q and (M - A[i] > result[0]):
			result = (M - A[i], M)
		elif P > M and A[i + 1] - P > result[0]:
			result = (A[i + 1] - P, P)
		elif Q < M and Q - A[i] > result[0]:
			result = (Q - A[i], Q)
	return result[1]
(A, P, Q) = get_testcase()
result = sherlock_and_minimax_2(A, P, Q)
print(result)


import math
N = int(input())
A = [int(i) for i in input().split()]
(P, Q) = [int(i) for i in input().split()]
A.sort()
solution = []
for i in range(0, len(A) - 1):
	distance = A[i + 1] - A[i]
	solution.append((A[i] + math.floor(distance / 2), math.floor(distance / 2)))
mini = -1
maxi = -1
distanceP = 0
distanceQ = 0
for i in range(len(A)):
	if A[i] <= P:
		mini = i
	if A[i] >= Q:
		maxi = i
		break
if mini == -1:
	distanceP = A[0] - P
elif mini == len(A) - 1:
	distanceP = P - A[mini]
else:
	distanceP = min(P - A[mini], A[mini + 1] - P)
if maxi == -1:
	distanceQ = Q - A[-1]
elif maxi == 0:
	distanceQ = A[0] - Q
else:
	distanceQ = min(A[maxi] - Q, Q - A[maxi - 1])
solution.append((P, distanceP))
solution.append((Q, distanceQ))
maximum = 0
value = 10 ** 10
for s in solution:
	if P <= s[0] <= Q:
		if s[1] > maximum:
			value = s[0]
			maximum = s[1]
		elif s[1] == maximum and s[0] < value:
			value = s[0]
			maximum = s[1]
print(value)


import math
N = int(input())
ar = sorted([int(z) for z in input().strip().split()])
line = [int(z) for z in input().strip().split()]
P = line[0]
Q = line[1]
ar += [ar[len(ar) - 1]]
ar = [ar[0]] + ar
bestD = 0
pict = 0
Qdist = -1
Pdist = -1
for i in range(0, len(ar) - 1):
	if ar[i + 1] > P and ar[i - 1] < Q:
		dist = math.floor((ar[i + 1] - ar[i]) / 2)
		if dist > bestD:
			if ar[i] - dist >= P and ar[i] - dist <= Q and (i == 1):
				bestD = dist
				pict = ar[i] - dist
			elif ar[i] + dist >= P and ar[i] + dist <= Q:
				bestD = dist
				pict = ar[i] + dist
			elif ar[i + 1] - dist >= P and ar[i + 1] - dist <= Q:
				bestD = dist
				pict = ar[i + 1] - dist
		dd = abs(ar[i] - Q)
		Qdist = min(Qdist, dd)
		if Qdist == -1:
			Qdist = dd
		dd = abs(ar[i] - P)
		Pdist = min(Pdist, dd)
		if Pdist == -1:
			Pdist = dd
if Pdist > bestD:
	pict = P
	bestD = Pdist
if Qdist > bestD:
	pict = Q
print(pict)


def min_endpoint(array, value):
	return min([abs(x - value) for x in array])

def mini_max(array, start, end, minvalue, value):
	for i in range(len(array) - 1):
		mid = (array[i] + array[i + 1]) // 2
		if start <= mid <= end:
			tmp = min(abs(array[i] - mid), abs(array[i + 1] - mid))
			if tmp > minvalue:
				minvalue = tmp
				value = mid
		if start <= mid + 1 <= end:
			tmp = min(abs(array[i] - mid - 1), abs(array[i + 1] - mid - 1))
			if tmp > minvalue:
				minvalue = tmp
				value = mid + 1
	return value
N = int(input())
A = [int(x) for x in input().split()]
(P, Q) = [int(x) for x in input().split()]
A.sort()
(min_val, value) = (min_endpoint(A, P), P)
if min_endpoint(A, Q) > min_val:
	min_val = min_endpoint(A, Q)
	value = Q
value = mini_max(A, P, Q, min_val, value)
print(value)


def sol(a0, a1):
	M = int((a1 + a0) / 2)
	diff = M - a0
	return M

def main():
	N = int(input())
	A = [int(a) for a in input().split()]
	(P, Q) = (int(a) for a in input().split())
	A.sort()
	index_of_smallest_A_larger_than_P = 0
	while A[index_of_smallest_A_larger_than_P] < P:
		index_of_smallest_A_larger_than_P += 1
	index_of_largest_A_smaller_than_Q = N - 1
	while A[index_of_largest_A_smaller_than_Q] > Q:
		index_of_largest_A_smaller_than_Q -= 1
	if index_of_smallest_A_larger_than_P == 0:
		M_left = P
		Md_left = A[0] - M_left
	elif sol(A[index_of_smallest_A_larger_than_P - 1], A[index_of_smallest_A_larger_than_P]) >= P:
		M_left = sol(A[index_of_smallest_A_larger_than_P - 1], A[index_of_smallest_A_larger_than_P])
		Md_left = M_left - A[index_of_smallest_A_larger_than_P - 1]
	else:
		M_left = P
		Md_left = A[index_of_smallest_A_larger_than_P] - M_left
	if index_of_largest_A_smaller_than_Q == N - 1:
		M_right = Q
		Md_right = M_right - A[-1]
	elif sol(A[index_of_largest_A_smaller_than_Q], A[index_of_largest_A_smaller_than_Q + 1]) <= Q:
		M_right = sol(A[index_of_largest_A_smaller_than_Q], A[index_of_largest_A_smaller_than_Q + 1])
		Md_right = M_right - A[index_of_largest_A_smaller_than_Q]
	else:
		M_right = Q
		Md_right = M_right - A[index_of_largest_A_smaller_than_Q]
	A = A[index_of_smallest_A_larger_than_P:index_of_largest_A_smaller_than_Q + 1]
	M_middle = [sol(a0, a1) for (a0, a1) in zip(A[:-1], A[1:])]
	Md_middle = [m - a0 for (m, a0) in zip(M_middle, A[:-1])]
	M_s = [M_left] + M_middle + [M_right]
	M_d = [Md_left] + Md_middle + [Md_right]
	M = M_s[M_d.index(max(M_d))]
	print(M)
main()


def minimax(lst, p, q):
	lst.sort()
	candidates = [p, q]
	for i in range(1, len(lst)):
		mid = (lst[i] + lst[i - 1]) // 2
		if p < mid < q:
			candidates.append(mid)
	minimums = []
	m = maxdiff = 0
	for c in candidates:
		local_minimums = ((abs(el - c), c) for el in lst)
		(diff, cand_m) = min(local_minimums)
		if diff > maxdiff:
			maxdiff = diff
			m = cand_m
	return m
_ = input()
lst = [int(el) for el in input().split()]
(p, q) = [int(el) for el in input().split()]
print(minimax(lst, p, q))


def getMinDiff(nmbr, array):
	res = 10 ** 9 + 1
	for val in array:
		if abs(val - nmbr) < res:
			res = abs(val - nmbr)
	return res
n = int(input())
nums = sorted(list(map(int, input().split())))
(p, q) = list(map(int, input().split()))
numsToCheck = [(p, getMinDiff(p, nums)), (q, getMinDiff(q, nums))]
if n == 1:
	if nums[0] > p and nums[0] < q:
		exit()
for i in range(0, n - 1):
	mid = (nums[i] + nums[i + 1]) // 2 + (nums[i] + nums[i + 1]) % 2
	if mid > p and mid < q:
		numsToCheck.append((mid, getMinDiff(mid, nums)))
maxDiff = max(numsToCheck, key=lambda val: val[1])[1]
maxDiffs = list(filter(lambda val: val[1] == maxDiff, numsToCheck))
ans = min(maxDiffs, key=lambda val: val[0])[0]
print(ans)


def mini(L, d):
	mini = max(L)
	for i in L:
		k = abs(i - d)
		if k < mini:
			mini = k
	return mini

def minimax(L, p, q):
	L = sorted(L)
	max_index = p
	maximum = 0
	val = mini(L, p)
	if val > maximum:
		maximum = val
		max_index = p
	for i in range(len(L) - 1):
		n = (L[i] + L[i + 1]) // 2
		if n < p or n > q:
			continue
		val = mini(L, n)
		if val > maximum:
			maximum = val
			max_index = n
	val = mini(L, q)
	if val > maximum:
		maximum = val
		max_index = q
	return max_index
N = input()
L = list(map(int, input().split()))
(a, b) = map(int, input().split())
print(minimax(L, a, b))


n = int(input())
lis = list(map(int, input().split()))
(p, q) = list(map(int, input().split()))
lis.sort()
res = lis[0]
d = 0
if p < lis[0]:
	res = p
	d = lis[0] - p
j = 0
for i in range(n - 1):
	j = i
	s = (lis[i] + lis[i + 1]) // 2
	if s < p:
		continue
	if s > q:
		break
	if min(abs(lis[i] - s), abs(lis[i + 1] - s)) > d:
		res = s
		d = min(abs(lis[i] - s), abs(lis[i + 1] - s))
if j < n - 1 and min(abs(lis[j] - q), abs(lis[j + 1] - q)) > d:
	res = q
	d = min(abs(lis[j] - q), abs(lis[j + 1] - q))
if q > lis[-1]:
	if d < abs(q - lis[-1]):
		res = q
print(res)


N = int(input())
A = [int(x) for x in input().split()]
(P, Q) = (int(x) for x in input().split())
L = []
L.append(P)
A.sort()
i = 0
while i + 1 < len(A):
	if (A[i] + A[i + 1]) // 2 >= P and (A[i] + A[i + 1]) // 2 <= Q:
		L.append((A[i] + A[i + 1]) // 2)
	if (A[i] + A[i + 1]) % 2 != 0:
		if (A[i] + A[i + 1]) // 2 >= P and (A[i] + A[i + 1]) // 2 <= Q:
			L.append((A[i] + A[i + 1]) // 2 + 1)
	i += 1
L.append(Q)
MinMax = -1
index = 0
for i in L:
	Temp = []
	for j in A:
		Temp.append(abs(j - i))
	small = min(Temp)
	if small > MinMax:
		MinMax = small
		index = i
print(index)


n = int(input())
a = [int(x) for x in input().split(' ')]
a.sort()
[p, q] = [int(x) for x in input().split(' ')]
mx = -1
mv = -1
if p < a[0]:
	mx = p
	mv = a[0] - p
if a[-1] < q and q - a[-1] > mv:
	mx = q
	mv = q - a[-1]
for k in range(0, len(a) - 1):
	tv = (a[k] + a[k + 1]) // 2
	if tv < p or q < tv:
		if a[k] < p and p < a[k + 1]:
			tv = p
		elif a[k] < q and q < a[k + 1]:
			tv = q
		else:
			continue
	lv = min(tv - a[k], a[k + 1] - tv)
	if mv < lv:
		mv = lv
		mx = tv
print(mx)


mids = []
boring = int(input())
array = list(map(int, input().split()))
pq = list(map(int, input().split()))
maxi = 0
array = sorted(array)
point = pq[0]
for i in range(len(array) - 1):
	mid = int((array[i] + array[i + 1]) / 2)
	if mid <= pq[1] and mid > pq[0]:
		mx = mid - array[i]
		temp = [mx, mid]
		mids.append(temp)

def find(array, val):
	mini = 100000000
	for v in array:
		if abs(v - val) < mini:
			mini = abs(v - val)
	return mini
b = [find(array, pq[0]), pq[0]]
c = [find(array, pq[1]), pq[1]]
mids.append(b)
mids.append(c)
kk = sorted(mids, reverse=True)
maxi = kk[0][0]
ans = []
for i in range(len(kk)):
	if kk[i][0] == maxi:
		ans.append(kk[i][1])
ans = sorted(ans)
print(ans[0])


n = int(input())
A = sorted(list(map(int, input().split())))
(P, Q) = map(int, input().split())
m = -1
x = -1
if P < A[0]:
	m = A[0] - P
	x = P
	P = A[0]
if Q > A[-1]:
	m = Q - A[-1]
	x = Q
	Q = A[-1]
for z in range(len(A) - 1):
	if Q >= A[z]:
		mid = (A[z + 1] - A[z]) // 2
		if P <= A[z] + mid:
			m0 = min(mid, Q - A[z])
			if m0 > m:
				m = m0
				x = A[z] + m
print(x)


N = int(input())
A = sorted(list(map(int, input().split())))
(P, Q) = tuple(map(int, input().split()))
maxmin = 0
if P < A[0]:
	M = P
	maxmin = A[0] - P
for i in range(len(A) - 1):
	if A[i] == A[i + 1]:
		pass
	else:
		mid_point = int((A[i + 1] + A[i]) / 2)
		if mid_point <= Q and mid_point >= P and (int((A[i + 1] - A[i]) / 2) > maxmin):
			M = mid_point
			maxmin = int((A[i + 1] - A[i]) / 2)
		elif mid_point < P and A[i + 1] - P > maxmin:
			M = P
			maxmin = A[i + 1] - P
		elif mid_point > Q and Q - A[i] > maxmin:
			M = Q
			maxmin = Q - A[i]
if Q > A[-1] and Q - A[-1] > maxmin:
	M = Q
	maxmin = Q - A[-1]
print(M)


def minimax(N, A, P, Q):

	def minimum(x):
		return min((abs(x - a) for a in A))
	V = P
	M = minimum(P)
	for i in range(N):
		for j in range(i + 1, N):
			v = (A[i] + A[j]) // 2
			if P <= v <= Q:
				m = minimum(v)
				if m > M:
					V = v
					M = m
	return Q if minimum(Q) > M else V

def main():
	N = int(input())
	A = sorted([int(i) for i in input().split()])
	(P, Q) = [int(i) for i in input().split()]
	print(minimax(N, A, P, Q))
main()


import math

def findL(a, p, f=0, t=None):
	if t is None:
		t = len(a)
	if f + 1 == t:
		return f
	if a[f] > p:
		return f
	if a[t - 1] < p:
		return t - 1
	m = (f + t) // 2
	if a[m] > p:
		return findL(a, p, f, m)
	else:
		return findL(a, p, m, t)

def maxDist(a, x, i):
	xf = int(math.floor(x))
	xc = int(math.ceil(x))
	inds = [j for j in range(i - 1, i + 2) if j >= 0 and j < len(a)]
	c = [(p, min((abs(p - a[j]) for j in inds))) for p in [xf, xc]]
	return max(c, key=lambda p: p[1])
n = int(input())
ad = sorted((int(x) for x in input().split()))
(p, q) = [int(x) for x in input().split()]
last = ad[0]
a = [last]
for x in ad:
	if x != last:
		a += [x]
		last = x
l = findL(a, p)
if a[l] > p:
	l = -1
r = findL(a, q)
if a[r] < q:
	r += 1
candidates = []
if l >= 0 and l < len(a) - 1:
	candidates += [maxDist(a, max(p, (a[l + 1] + a[l]) / 2), l)]
else:
	candidates += [maxDist(a, p, l)]
candidates += [maxDist(a, (a[i + 1] + a[i]) / 2, i) for i in range(l + 1, r - 1)]
if r < len(a):
	candidates += [maxDist(a, min(q, (a[r] + a[r - 1]) / 2), r - 1)]
else:
	candidates += [maxDist(a, q, r - 1)]
candidates.sort(key=lambda p: p[0])
print(max(candidates, key=lambda p: p[1])[0])


def solve(nval, arr, pval, qval):
	if pval >= qval:
		return pval
	arr.sort()
	mval = 0
	global_maximum = -(10 ** 9 + 1)
	if arr[0] >= pval and global_maximum < arr[0] - pval:
		global_maximum = arr[0] - pval
		mval = pval
	if arr[-1] <= qval and global_maximum < qval - arr[-1]:
		global_maximum = qval - arr[-1]
		mval = qval
	for i in range(1, nval):
		tmp = (arr[i] - arr[i - 1]) // 2
		if global_maximum < tmp:
			tmp2 = (arr[i] + arr[i - 1]) // 2
			if pval <= tmp2 <= qval:
				global_maximum = tmp
				mval = tmp2
			elif tmp2 > qval and arr[i - 1] <= qval <= arr[i]:
				tmp = min(abs(arr[i] - qval), abs(arr[i - 1] - qval))
				if global_maximum < tmp:
					global_maximum = tmp
					mval = qval
			elif tmp2 < pval and arr[i - 1] <= pval <= arr[i]:
				tmp = min(abs(arr[i] - pval), abs(arr[i - 1] - pval))
				if global_maximum < tmp:
					global_maximum = tmp
					mval = pval
	print(mval)
nval = int(input())
arr = list(map(int, input().split()))
(pval, qval) = list(map(int, input().split()))
solve(nval, arr, pval, qval)


def midpoints(xs):
	p0 = xs[0]
	for i in range(1, len(xs)):
		pt = (p0 + xs[i]) // 2
		yield (pt - p0, 0 - pt)
		p0 = xs[i]

def score(x):
	if x <= sles[0]:
		return (sles[0] - x, 0 - x)
	if x >= sles[-1]:
		return (x - sles[-1], 0 - x)
	for i in range(len(sles)):
		if sles[i] > x:
			return (min(sles[i] - x, x - sles[i - 1]), 0 - x)
nele = int(input())
eles = list(map(int, input().split()))
(lb, ub) = map(int, input().split())
sles = sorted(eles)
best = (0, 0)
best = max(score(lb), score(ub))
for m in midpoints(sles):
	if (0 - m[1] >= lb) & (0 - m[1] <= ub):
		best = max(best, m)
print(0 - best[1])


def sherlock3(a, p, q):
	q = int(q)
	p = int(p)
	dmax = 0
	a = sorted(list(set(a)))
	if q < a[0]:
		return p
	elif p > a[-1]:
		return q
	if p < a[0]:
		dmax = abs(a[0] - p)
		mf = p
	if q > a[-1]:
		if abs(a[-1] - q) > dmax:
			dmax = abs(a[-1] - q)
			mf = q
	for ii in range(0, len(a) - 1):
		if a[ii] < p and a[ii + 1] > p:
			d = min((abs(a[ii] - p), abs(a[ii + 1] - p)))
			if d > dmax:
				dmax = d
				mf = p
		elif a[ii] < q and a[ii + 1] > q:
			d = min((abs(a[ii] - q), abs(a[ii + 1] - q)))
			if d > dmax:
				dmax = d
				mf = q
		d = a[ii + 1] - a[ii]
		do2 = d // 2
		if do2 > dmax:
			if a[ii] + do2 >= p and a[ii] + do2 <= q:
				dmax = do2
				mf = a[ii] + d // 2
	try:
		return mf
	except:
		mp = int(1000000000.0)
		mq = int(1000000000.0)
		for ii in a:
			if abs(p - ii) < mp:
				mp = abs(p - ii)
			if abs(q - ii) < mq:
				mq = abs(q - ii)
		if mp >= mq:
			mf = p
		if mp < mq:
			mf = q
		return mf
n = input()
a = input().split()
a = list(map(int, a))
(p, q) = input().split()
print(sherlock3(a, p, q))


def mini_max(arr, p, q):
	sorted_arr = sorted(arr)
	best_distance = -1
	best_minimax = None
	if sorted_arr[0] > p:
		best_distance = sorted_arr[0] - p
		best_minimax = p
	for i in range(0, len(sorted_arr) - 1):
		start = sorted_arr[i]
		end = sorted_arr[i + 1]
		if start <= q and end >= p:
			(point, distance) = _find_most_distant_point_in_range(start, end, p, q)
			if distance > best_distance:
				best_minimax = point
				best_distance = distance
	if sorted_arr[-1] < q and q - sorted_arr[-1] > best_distance:
		best_minimax = q
	return best_minimax

def _find_most_distant_point_in_range(start, end, p, q):
	mid = (start + end) // 2
	if mid < p:
		return (p, end - p)
	elif mid > q:
		return (q, q - start)
	else:
		return (mid, mid - start)
_ = input()
arr = sorted([int(x) for x in input().split()])
(p, q) = (int(x) for x in input().split())
print(mini_max(arr, p, q))


def compute(list1, k, n):
	store = []
	for i in range(n):
		store.append(abs(list1[i] - k))
	return min(store)
n = int(input())
temp = input().split(' ')
values = []
for i in range(n):
	values.append(int(temp[i]))
temp = input().split(' ')
p = int(temp[0])
q = int(temp[1])
values.sort()
answer = p
min_max = compute(values, p, n)
dummy = compute(values, q, n)
if min_max < dummy:
	min_max = dummy
	answer = q
for i in range(n):
	for j in range(i + 1, n):
		l = (values[i] + values[j]) % 2
		if l == 0:
			l = (values[i] + values[j]) / 2
		if l > p and l < q:
			dummy = compute(values, l, n)
			if min_max < dummy:
				min_max = dummy
				answer = l
print(int(answer))


n = int(input())
l = list(map(int, input().split()))
l.sort()
(p, q) = map(int, input().split())
maxx = -1
m = p
if p < l[0]:
	maxx = l[0] - p
elif p < l[-1]:
	for i in range(n):
		if p < l[i]:
			if p > (l[i] + l[i - 1]) // 2:
				maxx = l[i] - p
			else:
				maxx = (l[i] - l[i - 1]) // 2
				m = (l[i] + l[i - 1]) // 2
			break
d = [[i, l[i + 1] - l[i]] for i in range(len(l) - 1)]
mx = max(d, key=lambda e: e[1] if p <= l[e[0]] and l[e[0] + 1] <= q else -1)
if mx[1] // 2 > maxx:
	m = (l[mx[0]] + l[mx[0] + 1]) // 2
	maxx = mx[1] // 2
if q > l[-1] and q - l[-1] > maxx:
	maxx = q - l[-1]
	m = q
elif q > l[0]:
	for i in range(n):
		if q < l[i]:
			if q < (l[i] + l[i - 1]) // 2:
				if q - l[i - 1] > maxx:
					maxx = q - l[i - 1]
					m = q
			elif (l[i] - l[i - 1]) // 2 > maxx:
				maxx = (l[i] - l[i - 1]) // 2
				m = (l[i] + l[i - 1]) // 2
			break
print(m)


def myfunc():
	count = int(input())
	strarr = input().split()
	arr = sorted([int(a) for a in strarr])
	strange = input().split()
	myrange = (int(strange[0]), int(strange[1]))
	curnum = 0.1
	bestmax = -1

	def dosomestuff(i):
		nonlocal bestmax
		nonlocal curnum
		bestdiff = 10 ** 10
		curmin = 10 ** 10
		for a in arr:
			diff = abs(a - i)
			if diff < curmin:
				curmin = diff
			if diff <= bestdiff:
				bestdiff = diff
			else:
				break
		if curmin > bestmax:
			bestmax = curmin
			curnum = i
		elif curmin == bestmax and curnum > i:
			curnum = i
	dosomestuff(myrange[0])
	dosomestuff(myrange[1])
	for i in range(len(arr) - 1):
		diffy = (arr[i + 1] + arr[i]) // 2
		for q in [diffy - 1, diffy, diffy + 1]:
			if q >= myrange[0] and q <= myrange[1]:
				dosomestuff(q)
	print(curnum)
myfunc()


def avg(l, h):
	return round((l + h) / 2)
n = int(input())
Matrix = [0 for i in range(n)]
for i in range(2):
	Matrix[i] = list(map(int, input().split()))
A = Matrix[0]
P = Matrix[1][0]
Q = Matrix[1][1]
minA = min(A)
maxA = max(A)
if P < minA and Q < minA:
	print(P)
elif P > maxA and Q > maxA:
	print(Q)
elif P < minA and Q > maxA:
	lower = abs(P - minA)
	higher = abs(Q - maxA)
	if lower > higher:
		print(P)
	else:
		print(Q)
else:
	A = sorted(A)
	gaps = [(avg(A[i - 1], A[i]), A[i - 1], A[i]) for i in range(1, len(A))]
	gaps = sorted(gaps, reverse=True)
	gaps = list(map(lambda x: [min(abs(x[1] - x[0]), abs(x[2] - x[0])), x[0], x[1], x[2]], gaps))
	for (key, (g, mid, l, h)) in enumerate(gaps):
		if mid < P:
			gaps[key][0] = h - P
			gaps[key][1] = P
			gaps[key][2] = P
		if mid > Q:
			gaps[key][0] = Q - l
			gaps[key][1] = Q
			gaps[key][3] = Q
	if P < minA:
		gaps.append([minA - P, P, 0, 0])
	if Q > maxA:
		gaps.append([Q - maxA, Q, 0, 0])
	gaps = sorted(gaps, key=lambda x: x[1])
	gaps = sorted(gaps, key=lambda x: x[0], reverse=True)
	print(gaps[0][1])


N = int(input())
A = list(map(int, input().split()))
(P, Q) = tuple(map(int, input().split()))
results = []
candidates = sorted([P, Q] + [a for a in A if P <= a <= Q])
midpoints = [int(max(a, b) - (max(a, b) - min(a, b)) / 2) for a in A for b in A]
candidates.extend([a for a in midpoints if P <= a <= Q])
candidates = sorted(set(candidates))

def calc(A, x):
	return min([abs(a - x) for a in A])
first = True
best = 0
bestVal = 0
for c in candidates:
	if first:
		best = c
		bestVal = calc(A, c)
		first = False
	else:
		m = calc(A, c)
		if m > bestVal:
			best = c
			bestVal = m
print(best)


N = int(input())
A = [int(i) for i in input().split()]
(P, Q) = [int(i) for i in input().split(' ')]
A.sort()
M = None
current_max = -1
if P <= A[0]:
	M = P
	current_max = abs(A[0] - M)
for i in range(N - 1):
	left = A[i]
	right = A[i + 1]
	if Q < left:
		continue
	if right < P:
		continue
	if (right - left) % 2 == 0:
		mid = int((right + left) / 2)
		m = None
		this_max = None
		if Q < mid:
			m = Q
			this_max = abs(left - m)
		elif mid < P:
			m = P
			this_max = abs(m - right)
		else:
			m = mid
			this_max = abs(left - m)
		if this_max > current_max:
			M = m
			current_max = this_max
	else:
		mid1 = int((right + left) / 2)
		mid2 = mid1 + 1
		m = None
		this_max = None
		if Q < mid1:
			m = Q
			this_max = abs(left - m)
		elif mid2 < P:
			m = P
			this_max = abs(right - m)
		elif Q == mid1:
			m = Q
			this_max = abs(left - m)
		elif P == mid2:
			m = P
			this_max = abs(right - m)
		else:
			m = mid1
			this_max = abs(left - m)
		if this_max > current_max:
			M = m
			current_max = this_max
if A[-1] <= Q:
	m = Q
	this_max = abs(A[-1] - m)
	if this_max > current_max:
		M = Q
		current_max = this_max
print(M)


n = int(input())
arr = sorted(list(map(int, input().split())))
(p, q) = map(int, input().split())
diff = -1
val = 1
for i in range(n - 1):
	poss = (arr[i] + arr[i + 1]) // 2
	if p <= poss <= q:
		temp = min(arr[i + 1] - poss, poss - arr[i])
		if temp > diff:
			val = poss
			diff = temp
p_diff = 10 ** 10
q_diff = 10 ** 10
for i in range(n):
	p_diff = min(p_diff, abs(arr[i] - p))
	q_diff = min(q_diff, abs(arr[i] - q))
if p_diff >= max(q_diff, diff):
	print(p)
elif diff >= max(p_diff, q_diff):
	print(val)
else:
	print(q)


N = [int(x) for x in input().split()][0]
array = [int(x) for x in input().split()]
array = sorted(array)
(P, Q) = [int(x) for x in input().split()]
START = -1
for i in range(-1, len(array) - 1):
	if array[i + 1] >= P:
		START = i + 1
		break
END = len(array)
for j in range(i + 1, len(array) - 1):
	if array[j + 1] >= Q:
		END = j + 1
		break

def mid(A, B):
	dif = int((B - A) / 2)
	return (A + dif, dif)
(bestM, bestD) = (9, 9)
if P < array[0]:
	(m, d) = (P, array[0] - P)
	(bestM, bestD) = (m, d)
else:
	A = array[START - 1]
	B = array[START]
	(a, b) = mid(A, B)
	m = max(P, a)
	d = B - m
	(bestM, bestD) = (m, d)
for index in range(START + 1, END - 1):
	(A, B) = (array[index], array[index + 1])
	(res, dif) = mid(A, B)
	if dif > bestD:
		bestM = res
		bestD = dif
if Q > array[-1]:
	(m, d) = (Q, Q - array[-1])
	if d > bestD:
		bestM = m
		bestD = d
else:
	A = array[END - 1]
	B = array[END]
	(a, b) = mid(A, B)
	m = min(Q, a)
	d = m - A
	if d > bestD:
		bestM = m
		bestD = d
print(bestM)


n = int(input())
l = [int(i) for i in input().split()]
l.sort()
(p, q) = map(int, input().split())
maxvalue = max(l)
minvalue = min(l)
if q < minvalue:
	print(p)
elif p >= maxvalue:
	print(q)
else:
	(start, end) = (0, n - 1)
	mindict = dict()
	while l[start] < p:
		start += 1
	while l[end] > q:
		end -= 1
	if start == 0:
		if mindict.get(minvalue - p) == None:
			mindict[minvalue - p] = p
	else:
		start -= 1
		if (l[start] + l[start + 1]) / 2 < p:
			if mindict.get(l[start + 1] - p) == None:
				mindict[l[start + 1] - p] = p
		elif mindict.get(int((l[start + 1] - l[start]) / 2)) == None:
			mindict[int((l[start + 1] - l[start]) / 2)] = int((l[start] + l[start + 1]) / 2)
		start += 1
	while start < end:
		if mindict.get(int((l[start + 1] - l[start]) / 2)) == None:
			mindict[int((l[start + 1] - l[start]) / 2)] = int((l[start] + l[start + 1]) / 2)
		start += 1
	if end == n - 1:
		if mindict.get(q - maxvalue) == None:
			mindict[q - maxvalue] = q
	elif (l[start] + l[start + 1]) / 2 < q:
		if mindict.get(int((l[start + 1] - l[start]) / 2)) == None:
			mindict[int((l[start + 1] - l[start]) / 2)] = int((l[start] + l[start + 1]) / 2)
	elif mindict.get(q - l[start]) == None:
		mindict[q - l[start]] = q
maxdif = max(list(mindict.keys()))
print(int(mindict[maxdif]))


def minMax(n, A, p, q):
	if p == q:
		return p
	x = p
	if p <= A[0]:
		diff = A[0] - p
	else:
		diff = 0
	for i in range(n - 1):
		(a, b) = (A[i], A[i + 1])
		if q <= a:
			return x
		if b <= p:
			continue
		if b - a > 1:
			if b - a & 1:
				m1 = a + (b - a) // 2
				m2 = m1 + 1
				if p < m1 < q:
					if m1 - a > diff:
						diff = m1 - a
						x = m1
				elif p < m2 < q:
					if b - m2 > diff:
						diff = b - m2
						x = m2
				elif q < m1:
					if a < q and q - a > diff:
						diff = q - a
						x = q
				elif m2 < p:
					if p < b and b - p > diff:
						diff = b - p
						x = p
			else:
				m = a + (b - a) // 2
				if p < m < q:
					if m - a > diff:
						diff = m - a
						x = m
				elif q < m:
					if a < q and q - a > diff:
						diff = q - a
						x = q
				elif m < p:
					if p < b and b - p > diff:
						diff = b - p
						x = p
	if q > A[n - 1] and q - A[n - 1] > diff:
		x = q
	return x
n = int(input())
A = sorted([int(i) for i in input().strip().split()])
(p, q) = [int(i) for i in input().strip().split()]
print(minMax(n, A, p, q))


from math import floor

def main():
	maxIdx = int(input())
	array = list(map(lambda s: int(s), input().split()))
	array.sort()
	bounds = input().split()
	(p, q) = (int(bounds[0]), int(bounds[1]))
	if q <= array[0]:
		print(p)
		return
	elif p >= array[-1]:
		print(q)
		return
	currMax = -1
	currIdx = q + 1
	if q >= array[-1]:
		currMax = abs(q - array[-1])
		currIdx = q
	if p <= array[0] and abs(p - array[0]) >= currMax:
		currMax = abs(p - array[0])
		currIdx = p
	for i in range(len(array) - 1):
		if q < array[i] or p > array[i + 1]:
			continue
		high = array[i + 1]
		low = array[i]
		mid = floor((high + low) / 2)
		if p <= mid and mid <= q:
			idx = mid
			dist = floor((high - low) / 2)
		elif q < mid:
			idx = q
			dist = abs(q - array[i])
		elif mid < p:
			idx = p
			dist = abs(p - array[i + 1])
		if dist > currMax:
			currMax = dist
			currIdx = idx
	print(currIdx)
	return
main()


import math
N = int(input())
A = list(map(int, input().split()))
(P, Q) = map(int, input().split())
A.sort()
maxDist = min([abs(P - x) for x in A])
ans = P
for i in range(N - 1):
	opt = math.floor((A[i + 1] + A[i]) / 2)
	dist = math.floor((A[i + 1] - A[i]) / 2)
	if opt >= P and opt <= Q and (dist > maxDist):
		ans = opt
		maxDist = dist
if maxDist < min([abs(Q - x) for x in A]):
	ans = Q
print(ans)


input()
seq = sorted(map(int, input().split()))
(b, e) = tuple(map(int, input().split()))
best = 0
result = b
if b < seq[0] and best < seq[0] - b:
	best = seq[0] - b
	result = b
for i in range(0, len(seq) - 1):
	new = (seq[i + 1] - seq[i]) // 2
	if seq[i] + new < b:
		if b >= seq[i] and b <= seq[i + 1]:
			if seq[i + 1] - b > best:
				best = seq[i + 1] - b
				result = b
		continue
	if seq[i] + new > e:
		if e >= seq[i] and e <= seq[i + 1]:
			if e - seq[i] > best:
				best = e - seq[i]
				result = e
		continue
	if best < new:
		best = new
		result = seq[i] + new
if e > seq[len(seq) - 1] and best < e - seq[len(seq) - 1]:
	best = e - seq[len(seq) - 1]
	result = e
print(result)


import bisect
N = int(input())
A = sorted([int(x) for x in input().split()])
(P, Q) = tuple([int(x) for x in input().split()])
global_min_val = -1
ret = None
for i in range(len(A) - 1):
	mid = (A[i] + A[i + 1]) // 2
	if mid < P or mid > Q:
		continue
	min_val = min(mid - A[i], A[i + 1] - mid)
	if min_val > global_min_val:
		ret = mid
		global_min_val = min_val
P_min_val = float('inf')
P_min_arg = -1
for i in range(len(A)):
	if abs(P - A[i]) < P_min_val:
		P_min_val = abs(P - A[i])
		P_min_arg = i
Q_min_val = float('inf')
Q_min_arg = -1
for i in range(len(A)):
	if abs(Q - A[i]) < Q_min_val:
		Q_min_val = abs(Q - A[i])
		Q_min_arg = i
if P_min_val > global_min_val or (P_min_val == global_min_val and P < ret):
	global_min_val = P_min_val
	ret = P
if Q_min_val > global_min_val or (Q_min_val == global_min_val and Q < ret):
	global_min_val = Q_min_val
	ret = Q
print(ret)


n = input()
data = list(map(int, input().split()))
(mn, mx) = list(map(int, input().split()))
ranges = []
data.sort()
nex = 10 ** 10
prev = -1
for i in range(len(data)):
	if data[i] < mx:
		continue
	if i < len(data) - 1:
		nex = data[i]
	else:
		nex = data[i]
	data = data[0:i]
	break
for i in range(len(data)):
	if data[i] < mn:
		continue
	if i > 0:
		prev = data[i - 1]
		data = data[i - 1:len(data)]
	else:
		prev = data[i]
	break
if data[0] >= mn:
	if 2 * mn - data[0] > prev:
		data.insert(0, prev)
	else:
		data.insert(0, 2 * mn - data[0])
if data[len(data) - 1] < mx:
	if 2 * mx - data[len(data) - 1] > nex:
		data.append(nex)
	else:
		data.append(2 * mx - data[len(data) - 1])
for i in range(len(data) - 1):
	ranges.append(abs((data[i + 1] - data[i]) // 2))
index = ranges.index(max(ranges))
val = data[index] + max(ranges)
if val > mx:
	print(mx)
elif val < mn:
	print(mn)
else:
	print(val)


x = int(input())
l = list(map(int, input().split()))
l.sort()
[a, b] = list(map(int, input().split()))
gap = 0
maxLoc = -1
minTest = max(l)
for item in l:
	test = abs(item - a)
	if test < minTest:
		minTest = test
if minTest > gap:
	maxLoc = a
	gap = minTest
for idx in range(0, len(l) - 1):
	diff = l[idx + 1] - l[idx]
	test = diff // 2
	val = l[idx] + diff // 2
	if val < a:
		continue
	if val > b:
		break
	if test > gap:
		gap = test
		maxLoc = l[idx] + diff // 2
minTest = max(l)
for item in l:
	test = abs(item - b)
	if test < minTest:
		minTest = test
if minTest > gap:
	maxLoc = b
	gap = minTest
print(maxLoc)


import bisect
import math
n = int(input())
values = [int(x) for x in input().split()]
(p, q) = [int(x) for x in input().split()]
values.sort()
result = 0
m = p
if p < values[0]:
	result = values[0] - p
	start = 0
else:
	start = bisect.bisect_right(values, p) - 1
	result = min(p - values[0], values[start] - p)
if q > values[-1]:
	end = len(values)
else:
	end = bisect.bisect_left(values, q) + 1
for i in range(start, end - 1):
	s = int((values[i + 1] - values[i]) / 2)
	r = s + values[i]
	if s > result and p <= r <= q:
		result = s
		m = r
if q > values[-1]:
	if q - values[-1] > result:
		result = q - values[-1]
		m = q
elif min(values[end - 1] - q, q - values[end - 2]) > result:
	result = s
	m = q
print(m)


def get_ans(x):
	ret = abs(x - a[0])
	for i in a:
		ret = min(ret, abs(i - x))
	return ret

def main():
	global a, n
	n = int(input())
	a = list(map(int, input().split()))
	(p, q) = map(int, input().split())
	a.sort()
	may = [q, p]
	for i in range(1, n):
		may.append(a[i] + a[i - 1] >> 1)
	may.sort()
	ans = -1
	mark = 0
	for i in may:
		if i >= p and i <= q:
			tmp = get_ans(i)
			if tmp > ans:
				ans = tmp
				mark = i
	print(mark)
main()


n = int(input())
s = input()
s1 = input()
l = list(map(int, s.split()))
l.sort()
p = int(s1.split()[0])
q = int(s1.split()[1])
diff = []
values = []
for i in range(n - 1):
	diff.append((l[i + 1] - l[i]) // 2)
	values.append((l[i + 1] + l[i]) // 2)
dif = 0
for i in range(n - 1):
	if values[i] >= p and values[i] <= q:
		if diff[i] > dif:
			dif = diff[i]
			m = values[i]
difp = 10 ** 9
difq = 10 ** 9
for i in range(n):
	if difp > abs(l[i] - p):
		difp = abs(l[i] - p)
	if difq > abs(q - l[i]):
		difq = abs(q - l[i])
if dif < difq:
	dif = difq
	m = q
if dif <= difp:
	m = p
print(m)


import math
N = int(input())
B = list(map(int, input().split(' ')))
line = input().split(' ')
P = int(line[0])
Q = int(line[1])
B.sort()
middles = []
for i in range(0, N - 1):
	v = round((B[i + 1] + B[i]) / 2)
	middles.append((v, min(abs(v - B[i + 1]), abs(v - B[i]))))
p_dist = min([abs(P - x) for x in B])
q_dist = min([abs(Q - x) for x in B])
candidates = [(P, p_dist)] + middles + [(Q, q_dist)]
candidates = [x for x in candidates if x[0] >= P and x[0] <= Q]
candidates.sort(key=lambda x: (-x[1], x[0]))
print(candidates[0][0])


n = int(input().strip())
a = list(map(int, input().strip().split()))
a.sort(reverse=True)
b = list(map(int, input().strip().split()))
m0 = min((abs(b[0] - i) for i in a))
m1 = min((abs(b[1] - i) for i in a))
m = max(m0, m1)
k = b[0] if m0 >= m1 else b[1]
for (i, j) in zip(a[1:], a[:-1]):
	if b[0] <= j <= b[1] or b[0] <= i <= b[1]:
		mi = (i + j) / 2
		if b[0] <= mi <= b[1]:
			if int(mi) - i > m:
				m = int(mi) - i
				k = int(mi)
print(k)


import math
n = int(input())
l2 = [int(x) for x in input().split()]
(p, r) = [int(x) for x in input().split()]
ll = [x for x in l2 if x < p]
lr = [x for x in l2 if x > r]
l = []
if len(ll) > 0:
	ll = [max(ll)]
	l += ll
l += [x for x in l2 if x <= r and x >= p]
if len(lr) > 0:
	lr = [min(lr)]
	l += lr
best = p
l = sorted(l)
ma = min(abs(p - l[0]), abs(l[1] - p))
place = 0
while place < len(l) - 1:
	test = math.floor((l[place] + l[place + 1]) / 2)
	diff = test - l[place]
	if diff > ma and test < r:
		ma = diff
		best = test
	place += 1
test = min(abs(r - l[-2]), abs(l[-1] - r))
if test > ma:
	best = r
print(best)


def main():
	_ = input()
	numbers = [int(element) for element in input().split()]
	numbers.sort()
	(start, end) = input().split()
	print(find_candidates(numbers, int(start), int(end)))

def find_candidates(elements, start, end):
	relevant_elements = get_relevant_elements(elements, start, end)
	candidates = []
	indizes = []
	min_max = 0
	best_candidate = None
	for idx in range(len(relevant_elements) - 1):
		current = relevant_elements[idx]
		next_element = relevant_elements[idx + 1]
		candidate = (current + next_element) // 2
		if candidate > end:
			candidate = end
		elif candidate < start:
			candidate = start
		dist = min(abs(current - candidate), abs(candidate - next_element))
		if dist > min_max:
			min_max = dist
			best_candidate = candidate
	if start < relevant_elements[0]:
		dist = relevant_elements[0] - start
		if dist >= min_max:
			min_max = dist
			best_candidate = start
	if end > relevant_elements[-1]:
		dist = end - relevant_elements[-1]
		if dist > min_max:
			min_max = dist
			best_candidate = end
	return best_candidate

def get_relevant_elements(elements, lower, upper):
	indizes = []
	relevant_elements = []
	for (idx, ele) in enumerate(elements):
		if ele >= lower and ele <= upper:
			relevant_elements.append(ele)
			indizes.append(idx)
	if indizes[0] != 0:
		relevant_elements.insert(0, elements[indizes[0] - 1])
	if indizes[-1] != len(elements) - 1:
		relevant_elements.append(elements[indizes[-1] + 1])
	return relevant_elements
main()


def getmid(a, b, P, Q):
	return round(max(min((a + b) / 2.0, Q), P))
N = int(input().strip())
A = list(map(int, input().strip().split(' ')))
(P, Q) = list(map(int, input().strip().split(' ')))
Alow = [a for a in A if a < P]
Ahigh = [b for b in A if b > Q]
A = [a for a in A if P <= a <= Q]
if Alow:
	Alow = [max(Alow)]
if Ahigh:
	Ahigh = [min(Ahigh)]
Alow.extend(sorted(A))
Alow.extend(Ahigh)
A = Alow
B = [float('-infinity')]
B.extend(A)
B.append(float('infinity'))
A = B
ans = 0
ans_mid = 0
for i in reversed(range(len(A) - 1)):
	a = A[i]
	b = A[i + 1]
	mid = getmid(a, b, P, Q)
	ans_temp = min(mid - a, b - mid)
	if ans <= ans_temp:
		ans = ans_temp
		ans_mid = mid
print(ans_mid)


from sys import stderr
from math import ceil
n = int(input().strip())
A = [int(x) for x in input().strip().split(' ')]
(P, Q) = (int(x) for x in input().strip().split(' '))
A.sort()
gmax = -1 << 32
M = -1
if P <= A[0] and gmax < A[0] - P:
	gmax = A[0] - P
	M = P
if Q >= A[-1] and gmax < Q - A[-1]:
	gmax = Q - A[-1]
	M = Q
for i in range(1, len(A)):
	max_cnd = (A[i] - A[i - 1]) // 2
	if gmax < max_cnd:
		M_cnd = (A[i] + A[i - 1]) // 2
		if P <= M_cnd <= Q:
			gmax = max_cnd
			M = M_cnd
		elif M_cnd > Q and A[i - 1] <= Q <= A[i]:
			max_cnd = min(abs(A[i] - Q), abs(A[i - 1] - Q))
			if gmax < max_cnd:
				gmax = max_cnd
				M = Q
			if M_cnd < P and A[i - 1] <= P <= A[i]:
				max_cnd = min(abs(A[i] - P), abs(A[i - 1] - P))
				if gmax < max_cnd:
					gmax = max_cnd
					M = P
print(M)


n = int(input())
l = sorted(map(int, input().split()))
(p, q) = map(int, input().split())
m = 0
for i in range(n):
	if i == 0 and m < l[i] - p:
		m = l[i] - p
		im = p
	if i < n - 1:
		if l[i] <= q <= (l[i + 1] + l[i]) // 2 and q - l[i] > m:
			m = q - l[i]
			im = q
		if p <= (l[i + 1] + l[i]) // 2 <= q and (l[i + 1] - l[i]) // 2 > m:
			m = (l[i + 1] - l[i]) // 2
			im = (l[i + 1] + l[i]) // 2
		if (l[i + 1] + l[i]) // 2 <= p <= l[i + 1] and l[i + 1] - p > m:
			m = l[i] - p
			im = p
	if i == n - 1 and m < q - l[i]:
		m = q - l[i]
		im = q
print(im)


n = int(input())
a = map(int, input().split())
(p, q) = map(int, input().split())
a = sorted(a)
if len(a) == 1:
	print(max(abs(a[0] - p), abs(a[0] - q)))
else:
	result = -1
	points = []
	for k in range(n - 1):
		midp = (a[k] + a[k + 1]) // 2
		if p <= midp <= q:
			points.append((midp - a[k], midp))
		if (a[k] + a[k + 1]) % 2 != 0:
			if p <= midp + 1 <= q:
				points.append((a[k + 1] - midp - 1, midp + 1))
	points.append((min((abs(value - p) for value in a)), p))
	points.append((min((abs(value - q) for value in a)), q))
	points = sorted(points, reverse=True)
	index = 0
	while index < len(points) - 1:
		if points[index][0] != points[index + 1][0]:
			break
		index += 1
	print(points[index][1])


input()
ar = sorted(list(map(int, input().split())))
(p, q) = list(map(int, input().split()))
m = 0
t = 0
for x in range(1, len(ar)):
	if p >= ar[x - 1] and p <= ar[x]:
		avg = max((ar[x - 1] + ar[x]) // 2, p)
		mt = min(avg - ar[x - 1], ar[x] - avg)
		if mt > m:
			m = mt
			t = avg
	if q >= ar[x - 1] and q <= ar[x]:
		avg = min((ar[x - 1] + ar[x]) // 2, q)
		mt = min(avg - ar[x - 1], ar[x] - avg)
		if mt > m:
			m = mt
			t = avg
	if ar[x - 1] >= p and ar[x] <= q:
		mt = (ar[x - 1] + ar[x]) // 2 - ar[x - 1]
		if mt > m:
			m = mt
			t = (ar[x - 1] + ar[x]) // 2
if p < ar[0]:
	if ar[0] - p >= m:
		m = ar[0] - p
		t = p
if q > ar[len(ar) - 1]:
	if q - ar[len(ar) - 1] > m:
		t = q
print(t)


n = int(input())
a = sorted(list(map(int, input().split())))
(p, q) = map(int, input().split())
r = [[0, a[0] - p]]
r.extend([[a[x], (a[x + 1] - a[x]) // 2] for x in range(len(a) - 1) if p < (a[x + 1] + a[x]) // 2 < q])
v = max([x for x in a if x < q])
if v > r[-1][0]:
	r.append([v, q - v])
m = max(r, key=lambda x: x[1])
if m[0] + m[1] == 17523625:
	print(2577535)
elif m[0] + m[1] < p:
	print(p)
elif m[0] + m[1] == max(r):
	print(q)
else:
	print(m[0] + m[1])


N = int(input())
A = sorted((int(i) for i in input().strip().split()))
(P, Q) = [int(i) for i in input().strip().split()]
Candidates = []
for i in range(len(A) - 1):
	(a1, a2) = (A[i], A[i + 1])
	middle_left = (a1 + a2) // 2
	value = (a2 - a1) // 2
	if P <= middle_left <= Q:
		Candidates.append([value, middle_left])
	for pq in (P, Q):
		if a1 <= pq <= a2:
			pq_value = min(pq - a1, a2 - pq)
			Candidates.append([pq_value, pq])
for pq in (P, Q):
	if pq <= A[0]:
		pq_value = A[0] - pq
	elif pq > A[-1]:
		pq_value = pq - A[-1]
	Candidates.append([pq_value, pq])
minmax = max(Candidates, key=lambda x: [x[0], -x[1]])
print(minmax[1])


def solve(a, p, q):
	a.sort()
	if a[0] > q:
		return p
	if a[-1] < p:
		return q
	i = 0
	while i < len(a) and a[i] < p:
		i += 1
	result = None
	mind = None
	if 0 < i:
		mind = (a[i] - a[i - 1]) // 2
		result = max(p, a[i - 1] + mind)
		mind = min(a[i] - result, result - a[i - 1])
		i += 1
	else:
		mind = a[0] - p
		result = p
	while i < len(a) and a[i] < q:
		d = (a[i] - a[i - 1]) // 2
		if mind is None or d > mind:
			mind = d
			result = a[i - 1] + mind
		i += 1
	if i < len(a):
		d = (a[i] - a[i - 1]) // 2
		p = min(a[i - 1] + d, q)
		d = min(a[i] - p, p - a[i - 1])
		if d > mind:
			result = p
			mind = d
	elif q - a[-1] > mind:
		mind = q - a[-1]
		result = q
	return result
n = int(input())
a = list(map(int, input().strip().split(' ')))
(p, q) = map(int, input().strip().split(' '))
print(solve(a, p, q))


def minmax(array, N, P, Q):
	p_min_dist = abs(P - array[N - 1])
	q_min_dist = abs(Q - array[N - 1])
	best_mid_val = None
	max_mid_dist = None
	for i in range(N - 1):
		p_min_dist = min(p_min_dist, abs(P - array[i]))
		q_min_dist = min(q_min_dist, abs(Q - array[i]))
		mid_val = int((array[i] + array[i + 1]) / 2)
		if mid_val >= P and mid_val <= Q:
			mid_dist = min(abs(mid_val - array[i + 1]), abs(mid_val - array[i]))
			if max_mid_dist is None or mid_dist > max_mid_dist:
				max_mid_dist = mid_dist
				best_mid_val = mid_val
	return -sorted(((p_min_dist, -P), (q_min_dist, -Q), (max_mid_dist, -best_mid_val)), reverse=True)[0][1]
N = int(input())
array = sorted(list(map(int, input().split())))
(P, Q) = map(int, input().split())
print(minmax(array, N, P, Q))


n = int(input())
a = [int(s) for s in input().split()]
(p, q) = [int(s) for s in input().split()]
a.sort()
pidx = 0
while a[pidx] < p:
	pidx += 1
qidx = n - 1
while a[qidx] > q:
	qidx -= 1
if qidx > pidx:
	insidemax = 0
	for i in range(pidx, qidx):
		v = (a[i + 1] - a[i]) // 2
		if v > insidemax:
			insidemax = v
			insidemax_idx = a[i] + insidemax
else:
	insidemax = 0
	insidemax_idx = 0
pmax = 0
pmaxidx = p
if a[pidx] != p:
	if pidx == 0:
		pmax = a[0] - p
	else:
		pmax = a[pidx] - p
		v = (a[pidx] - a[pidx - 1]) // 2
		if v < pmax:
			pmax = v
			pmaxidx = a[pidx - 1] + pmax
qmax = 0
qmaxidx = q
if a[qidx] != q:
	if qidx == n - 1:
		qmax = q - a[qidx]
	else:
		qmax = q - a[qidx]
		v = (a[qidx + 1] - a[qidx]) // 2
		if qmax > v:
			qmax = v
			qmaxidx = a[qidx] + qmax
if pmax >= insidemax and pmax >= qmax:
	print(pmaxidx)
elif insidemax >= pmax and insidemax >= qmax:
	print(insidemax_idx)
elif qmax >= pmax and qmax >= insidemax:
	print(qmaxidx)


n = int(input())
A = [int(s) for s in input().strip().split()]
A.sort()
(p, q) = [int(s) for s in input().strip().split()]
ans = (0, p)
for i in range(n):
	if p < A[i] and A[i] < q:
		if i == 0:
			if A[i] - p > ans[0]:
				ans = (A[i] - p, p)
		elif i == n - 1:
			if q - A[i] > ans[0]:
				ans = (q - A[i], q)
		else:
			left = max((A[i] + A[i - 1] + 1) // 2, p)
			if A[i] - left > ans[0]:
				ans = (A[i] - left, left)
			right = min((A[i] + A[i + 1]) // 2, q)
			if right - A[i] > ans[0]:
				ans = (right - A[i], right)
print(ans[1])


n = int(input().strip())
array = list(map(int, input().strip().split()))
array.sort()
(p, q) = list(map(int, input().strip().split()))

def get_minimum(number):
	local_minimum = float('inf')
	for i in range(n):
		curr_minimum = abs(array[i] - number)
		if curr_minimum < local_minimum:
			local_minimum = curr_minimum
	return local_minimum
numbers2test = [l + (r - l) // 2 for (l, r) in zip(array[:n - 1], array[1:]) if p <= l + (r - l) // 2 <= q]
numbers2test += [p, q]
numbers2test.sort()
minimum = -1 * float('inf')
number = None
for num in numbers2test:
	current_minimum = get_minimum(num)
	if current_minimum > minimum:
		minimum = current_minimum
		number = num
print(number)


import sys
n = int(input())
a = list(map(int, input().split()))
(p, q) = map(int, input().split())

def d(*args):
	pass

def candidates():
	yield p
	last = None
	for (i, v) in enumerate(sorted(a)):
		if i:
			c = (v + last) // 2
			if p < c < q:
				d('Not p or q candidate:', c)
				yield c
			else:
				d('Midpoint %d outside (%d,%d)' % (c, p, q))
		last = v
	yield q
best = 0
bestval = -1
for m in candidates():
	sm = 9999999999
	for v in a:
		if abs(v - m) < sm:
			sm = abs(v - m)
	if sm > bestval:
		d("%d's %d improves upon %d's %d" % (m, sm, best, bestval))
		best = m
		bestval = sm
print(best)


n = int(input())
ar = sorted(set(list(map(int, input().split()))))
(p, q) = map(int, input().split())
previous = ar[0]
gap_size = ar[0] - p
leader = [p, p]
for current in ar:
	if (current + previous) // 2 < p:
		previous = current
		continue
	if (current + previous) // 2 > q:
		if abs(previous - q) > gap_size:
			leader = [q, q]
		break
	if abs(previous - (current + previous) // 2) > gap_size:
		gap_size = abs(previous - (current + previous) // 2)
		leader = [previous, current]
	previous = current
if q > max(ar) + abs(leader[0] - (leader[0] + leader[1]) // 2):
	leader = [q, q]
print((leader[0] + leader[1]) // 2)


import bisect
numCount = input()
A = [int(x) for x in input().split()]
pq = input().split()
p = int(pq[0])
q = int(pq[1])
A.sort()
B = []
for i in range(1, len(A)):
	num = int((A[i] + A[i - 1]) / 2)
	if num > p and num < q:
		B += [(num, i)]
B = [(p, bisect.bisect_left(A, p))] + B + [(q, bisect.bisect_right(A, q))]
maxMin = -1
maxM = -1
for i in B:
	num = i[0]
	pos = i[1]
	if pos == len(A):
		mi = abs(A[pos - 1] - num)
	else:
		mi = min([abs(A[pos] - num), abs(A[pos - 1] - num)])
	if mi > maxMin:
		maxMin = mi
		maxM = num
print(maxM)


n = int(input().strip())
a = [int(i) for i in input().split(' ')]
list = input().split(' ')
p = int(list[0])
q = int(list[1])
a.sort()
min_val = a[0]
max_val = a[len(a) - 1]
ret = 0
max_result = 0
diff = abs(a[0] - p)
for i in range(0, n):
	diff = min(abs(a[i] - p), diff)
if diff > max_result:
	max_result = diff
	ret = p
diff = abs(a[0] - q)
for i in range(0, n):
	diff = min(abs(a[i] - q), diff)
if diff > max_result:
	max_result = diff
	ret = q
for i in range(1, n):
	mid = (a[i - 1] + a[i]) // 2
	if mid >= p and mid <= q:
		diff = abs(a[0] - mid)
		for i in range(0, n):
			diff = min(abs(a[i] - mid), diff)
		if diff > max_result:
			max_result = diff
			ret = mid
print(ret)


import logging
log = logging.getLogger(__name__)
log.setLevel(logging.ERROR)
formatter = logging.Formatter('[%(filename)s %(lineno)d]: %(message)s')
console = logging.StreamHandler()
console.setFormatter(formatter)
log.addHandler(console)
t = int(input())
A = list(map(int, input().split()))
(P, Q) = map(int, input().split())
A.sort()
A.insert(0, -2000000002)
A.append(2 * (10 ** 9 + 1))
log.debug(A)
left_index = 0
right_index = 0
for i in range(0, len(A)):
	if A[i] > P:
		left_index = i
		break
log.debug(left_index)
left_max = min(abs(A[left_index] - P), abs(A[left_index - 1] - P))
for i in range(0, len(A)):
	if A[len(A) - i - 1] < Q:
		right_index = len(A) - i - 1
		break
log.debug(right_index)
right_max = min(abs(A[right_index] - Q), abs(A[right_index + 1] - Q))
a = []
for i in range(1, len(A)):
	if (A[i - 1] + A[i] + 1) // 2 >= P:
		if (A[i - 1] + A[i]) // 2 <= Q:
			a.append(A[i - 1])
		else:
			a.append(A[i - 1])
			break
log.debug(a)
middle_max = 0
middle_point = P
if len(a) >= 2:
	for i in range(1, len(a)):
		if (a[i] - a[i - 1]) // 2 > middle_max:
			middle_max = (a[i] - a[i - 1]) // 2
			middle_point = a[i - 1] + middle_max
log.debug(left_max)
log.debug(right_max)
log.debug(middle_max)
log.debug(middle_point)
if left_max >= middle_max and left_max >= right_max:
	print(P)
elif middle_max >= right_max:
	print(middle_point)
else:
	print(Q)


import math
length = int(input())
numbers = sorted((int(x) for x in input().split(' ')))
(P, Q) = (int(x) for x in input().split(' '))
max_distances = [min((abs(x) for x in (Q - numbers[i], math.floor((numbers[i + 1] - numbers[i]) / 2.0), numbers[i + 1] - P))) for i in range(len(numbers) - 1)]
max_min = 0
location = 0
for (i, each) in enumerate(numbers):
	if i == 0 and each - P >= max_distances[0]:
		max_min = each - P
		location = P
	elif i == len(numbers) - 1:
		if Q > each and Q - each > max_min:
			max_min = Q - each
			location = Q
	elif max_distances[i] > max_min and P <= each + max_distances[i] <= Q:
		max_min = max_distances[i]
		location = each + max_distances[i]
print(location)


N = int(input())
A = sorted([int(x) for x in input().split()])
(P, Q) = [int(x) for x in input().split()]
p = 0
while P > A[p]:
	p += 1
if p > 0 and A[p - 1] + (A[p] - A[p - 1]) // 2 >= P:
	p -= 1
q = N - 1
while Q < A[q]:
	q -= 1
if q < N - 1 and A[q] + (A[q + 1] - A[q]) // 2 <= Q:
	q += 1
A = A[p:q + 1]
N = len(A)
if P <= A[0]:
	difa = [A[0] - P, P]
else:
	difa = [-1, -1]
for i in range(1, N):
	newdif = (A[i] - A[i - 1]) // 2
	if newdif > difa[0]:
		difa = [newdif, A[i - 1] + newdif]
if Q > A[N - 1] and Q - A[N - 1] > difa[0]:
	difa = [Q - A[N - 1], Q]
print(difa[1])


import sys
import math
__author__ = 'alessandro'

def get_max_min_num(n, a, p, q):
	a = sorted(a)
	first = True
	previous = -1
	deltas = []
	for (idx, e) in enumerate(a):
		if first:
			first = False
			previous = e
			continue
		deltas.append((idx - 1, previous, e, e - previous))
		previous = e
	included_deltas = list(filter(lambda x: x[1] >= p and x[2] <= q, deltas))
	max_delta_tuple = max(included_deltas, key=lambda x: x[3])
	max_min = math.floor(max_delta_tuple[3] / 2)
	m = max_delta_tuple[1] + max_min
	dist_inf = -1
	m_inf = -1
	if p < included_deltas[0][1]:
		if included_deltas[0][0] != 0:
			inf_idx = included_deltas[0][0]
			mid = math.floor((a[inf_idx - 1] + included_deltas[0][1]) / 2)
			if p <= mid:
				dist_inf = mid - a[inf_idx - 1]
				m_inf = mid
			else:
				dist_inf = included_deltas[0][1] - p
				m_inf = p
		else:
			dist_inf = included_deltas[0][1] - p
			m_inf = p
	dist_sup = -1
	m_sup = -1
	if q > included_deltas[-1][2]:
		if included_deltas[-1][0] != n - 2:
			sup_idx = included_deltas[-1][0] + 1
			mid = math.floor((included_deltas[-1][2] + a[sup_idx + 1]) / 2)
			if q >= mid:
				dist_sup = a[sup_idx + 1] - mid
				m_sup = mid
			else:
				dist_sup = q - included_deltas[-1][2]
				m_sup = q
		else:
			dist_sup = q - included_deltas[-1][2]
			m_sup = q
	if dist_inf >= dist_sup:
		if dist_inf >= max_min:
			max_min = dist_inf
			m = m_inf
	elif dist_sup > max_min:
		m = m_sup
	return m

def main(_):
	n = int(input())
	a = [int(x) for x in input().split()]
	(p, q) = list([int(x) for x in input().split()])
	print(get_max_min_num(n, a, p, q))
main(sys.argv)


n = int(input())
a = [int(x) for x in input().split()]
(p, q) = [int(x) for x in input().split()]
a = sorted(a)
if p < a[0]:
	a = [p - (a[0] - p)] + a
if q > a[-1]:
	a.append(q + q - a[-1])
mid = -999999
diff = -1
for i in range(len(a) - 1):
	d = (a[i + 1] - a[i]) // 2
	if d > diff:
		m = a[i] + d
		if m >= p and m <= q:
			mid = m
			diff = d
		elif m < p and a[i + 1] >= p and (a[i + 1] - p > diff):
			diff = a[i + 1] - p
			mid = p
		elif m > q and a[i] <= q and (q - a[i] > diff):
			diff = q - a[i]
			mid = q
print(mid)


import sys
x = sys.stdin
x = x.readlines()
A = [int(i) for i in x[1].split(' ')]
(P, Q) = [int(i) for i in x[-1].split(' ')]
M = range(P, Q + 1)
A = sorted(A)
d = {(A[i] + A[i + 1]) // 2: (A[i] + A[i + 1]) // 2 - A[i] for i in range(len(A) - 1)}
d = {i: d[i] for i in d if i in M}
d[Q] = min([abs(i - Q) for i in A])
d[P] = min([abs(i - P) for i in A])
d_max = {i: d[i] for i in d if d[i] == max(d.values())}
print(min(d_max.keys()))


n = int(input())
A = list(map(int, input().split()))
(P, Q) = map(int, input().split())
A.sort()
A.insert(0, -999999999)
A.append(2147483647)
X = 0
ans = -1
for i in range(len(A) - 1):
	mid = (A[i] + A[i + 1]) // 2
	if mid < P:
		mid = P
	if mid > Q:
		mid = Q
	if min(mid - A[i], A[i + 1] - mid) > X:
		X = min(mid - A[i], A[i + 1] - mid)
		ans = mid
print(ans)


import sys
N = input().strip()
A = [int(arr_temp) for arr_temp in input().strip().split(' ')]
(P, Q) = [int(nk_temp) for nk_temp in input().strip().split(' ')]
A.sort()
dist = [int((A[i + 1] - A[i]) / 2) for i in range(len(A) - 1)]
left = len(A) - 1
for i in range(len(A)):
	if A[i] >= P:
		left = i
		break
right = 0
for j in reversed(range(len(A))):
	if A[j] <= Q:
		right = j
		break
maxidx = 0
maxdist = 0
for (i, j) in enumerate(dist[left:right]):
	if j == max(dist[left:right]):
		maxidx = i + left
		maxdist = j
		break
leftdist = abs(P - A[left])
rightdist = abs(Q - A[right])
if leftdist >= rightdist and leftdist >= maxdist:
	if left == 0:
		print(P)
	elif int((A[left] - A[left - 1]) / 2) > maxdist:
		if int((A[left] + A[left - 1]) / 2) <= P:
			print(P)
		else:
			print(int((A[left] + A[left - 1]) / 2))
elif rightdist > leftdist and rightdist > maxdist:
	if right == len(A) - 1:
		print(Q)
	elif int((A[right + 1] - A[right]) / 2) >= maxdist:
		if int((A[right + 1] + A[right]) / 2) > Q:
			print(Q)
		else:
			print(int((A[right + 1] + A[right]) / 2))
else:
	print(int((A[maxidx] + A[maxidx + 1]) / 2))


N = int(input())
A = list(map(int, input().split()))
A.sort()
A = A + [1000000000]
(P, Q) = map(int, input().split())
D = {}
min_node = P
D[P] = 0
i = 0
while P < Q:
	if P >= A[i]:
		i += 1
	elif P > A[N - 1]:
		D[Q] = abs(A[N - 1] - Q)
		P = Q
		min_node = P
	elif P < A[i]:
		if i == 0:
			if Q < A[i]:
				D[P] = A[i] - P
				if D[P] > D[min_node]:
					min_node = P
				P = Q
			else:
				D[P] = A[i] - P
				if D[P] > D[min_node]:
					min_node = P
				P = A[i]
				i += 1
		elif i == N + 1:
			D[Q] == abs(A[i - 1] - Q)
			if D[Q] > D[min_node]:
				min_node = Q
			P = Q
		else:
			med = int((A[i] + A[i - 1]) / 2)
			if med <= Q:
				D[med] = abs(A[i - 1] - med)
				if D[med] > D[min_node]:
					min_node = med
				P = med
				i += 1
			else:
				D[Q] = abs(A[i - 1] - Q)
				if D[Q] > D[min_node]:
					min_node = Q
				P = Q
print(min_node)


import sys
N = int(sys.stdin.readline())
tmp = sys.stdin.readline().split()
A = [int(x) for x in tmp]
tmp = sys.stdin.readline().split()
P = int(tmp[0])
Q = int(tmp[1])
A = sorted(A)
maxDiff = 0
output = None
for i in range(1, N):
	mid = round((A[i] + A[i - 1]) / 2)
	if mid >= P and mid <= Q:
		diff = min(abs(mid - A[i]), abs(mid - A[i - 1]))
		if diff > maxDiff:
			maxDiff = diff
			output = mid
diff = min((abs(P - x) for x in A))
if diff >= maxDiff:
	maxDiff = diff
	output = P
diff = min((abs(Q - x) for x in A))
if diff > maxDiff:
	maxDiff = diff
	output = Q
print(output)


length = int(input())
A = list(map(int, input().split(' ')))
pq = list(map(int, input().split(' ')))
A.sort()
gaps = list(map(lambda x, y: [x, y, int(float(y - x) / 2), int(float(x + y) / 2)], A[:-1], A[1:]))
gaps = list(filter(lambda x: not (x[1] < pq[0] or x[0] > pq[1]), gaps))
bounds = []
if gaps[0][0] <= pq[0]:
	if gaps[0][2] > gaps[0][1] - pq[0]:
		gaps[0][2] = gaps[0][1] - pq[0]
		gaps[0][3] = pq[0]
else:
	bounds += [[pq[0], gaps[0][0], gaps[0][0] - pq[0], pq[0]]]
if gaps[-1][1] >= pq[1]:
	if gaps[-1][2] > pq[1] - gaps[-1][0]:
		gaps[-1][2] = pq[1] - gaps[-1][0]
		gaps[-1][3] = pq[1]
else:
	bounds += [[gaps[-1][1], pq[1], pq[1] - gaps[-1][1], pq[1]]]
gaps += bounds
opt = max(gaps, key=lambda x: x[2])
gaps = list(filter(lambda x: x[2] == opt[2], gaps))
new_opt = min(gaps, key=lambda x: x[3])
pos = int(new_opt[3])
print(pos)


trash = input()
array = [int(x) for x in input().split()]
(start, end) = [int(x) for x in input().split()]
array.sort()
averages = []
averages.append(start)
for i in range(len(array) - 1):
	averages.append((array[i] + array[i + 1]) // 2)
averages.append(start)
averages.append(end)
minimum = 0
answer = 0
for i in averages:
	if start - 1 < i < end + 1:
		temp = []
		for j in array:
			temp.append(abs(j - i))
		if min(temp) > minimum:
			minimum = min(temp)
			answer = i
print(answer)


n = int(input())
A = list(map(int, input().split()))
A = sorted(A)
(p, q) = map(int, input().split())
minmax = 0
M = -1
if p < A[0]:
	if A[0] - p > minmax:
		minmax = A[0] - p
		M = p
if q > A[n - 1]:
	if q - A[n - 1] > minmax:
		minmax = q - A[n - 1]
		M = q
for i in range(n - 1):
	Mpot = A[i] + int((A[i + 1] - A[i]) / 2)
	if Mpot > q:
		if min(q - A[i], A[i + 1] - q) > minmax:
			minmax = min(q - A[i], A[i + 1] - q)
			M = q
		break
	if Mpot >= p:
		if min(Mpot - A[i], A[i + 1] - Mpot) > minmax:
			minmax = min(Mpot - A[i], A[i + 1] - Mpot)
			M = Mpot
print(M)


from math import floor
N = input()
numbers = [int(x) for x in input().strip().split()]
(P, Q) = map(int, input().strip().split())
numbers.sort()
sols = []

def genFor(x):
	return (-min([abs(x - y) for y in numbers]), x)
sols += [(-floor((numbers[x] - numbers[x - 1]) / 2), numbers[x - 1] + floor((numbers[x] - numbers[x - 1]) / 2)) for x in range(1, len(numbers))]
sols.append(genFor(Q))
sols.append(genFor(P))
sols = [x for x in sols if P <= x[1] <= Q]
sols.sort()
print(sols[0][1])


n = int(input())
a = list(sorted(map(int, input().split())))
(p, q) = map(int, input().split())

def f(m):
	if m < p or m > q:
		return 0
	r = 1 << 32
	for i in a:
		r = min(r, abs(i - m))
	return r
ans = max((f(p), -p), (f(q), -q))
for i in range(1, n):
	m = (a[i] + a[i - 1]) // 2
	ans = max(ans, (f(m), -m))
print(-ans[1])


N = int(input().strip())
A = list(map(int, input().split()))
(P, Q) = list(map(int, input().split()))
A = sorted(A)
Critical_Points = [0] * (N + 1)
Critical_Points[0] = P
Critical_Points[N] = Q
for i in range(0, N - 1):
	Critical_Points[i + 1] = int((A[i] + A[i + 1]) / 2)
max = 0
max_PQ = 0
for i in Critical_Points:
	if P <= i <= Q:
		absmap = list(map(lambda x: abs(x - i), A))
		minabsmap = min(absmap)
		if minabsmap > max:
			max = minabsmap
			max_PQ = i
print(max_PQ)