def sherlockAndMinimax(arr, p, q):
    arr.sort()
    diff = -float('inf')
    ans = 0 
    if p < arr[0]:
        diff = arr[0] - p 
        ans = p 
    n = len(arr)
    for i in range(1,n):
        x = min(q, (arr[i] + arr[i-1])//2 )
        x = max(p, x)
        dif1 = arr[i] - x 
        dif2 = x - arr[i-1]
        y = min(dif1, dif2)
        if y > diff :
            if dif2 == y :
                diff = dif2
                ans = x
            else :
                diff = dif1
                ans = x
    if arr[-1] < q : 
        x = q - arr[-1]
        if x > diff :
            ans = q
    return ans