def sherlockAndMinimax(arr, p, q):
    arr.sort()
    n = len(arr)

    # Evaluate the endpoints p and q
    candidates = [p, q]

    # Evaluate midpoints between adjacent array elements
    for i in range(n - 1):
        mid = (arr[i] + arr[i + 1]) // 2
        if p <= mid <= q:
            candidates.append(mid)
        if p <= mid + 1 <= q:
            candidates.append(mid + 1)
    
    # Function to find the minimum distance to any array element
    def min_distance(M):
        return min(abs(M - x) for x in arr)
    
    # Evaluate each candidate and keep track of the best one
    best_M = None
    best_min_distance = -1

    for M in candidates:
        current_min_distance = min_distance(M)
        if (current_min_distance > best_min_distance) or (current_min_distance == best_min_distance and (best_M is None or M < best_M)):
            best_M = M
            best_min_distance = current_min_distance

    return best_M