int sherlockAndMinimax(vector<int> arr, int p, int q) {
    pair<int, int> M = {p, 0};
    sort(arr.begin(), arr.end());
    int first = -1, caseB = -1;
    bool flag = false;
    for (int i=0; i < arr.size(); i++) {
        if (arr[i] >= p and arr[i] <= q) {
            first = i;
            flag = true;
            break;
        }
        if (i < arr.size()-1 and arr[i] < p and arr[i+1] > q){
            caseB = i;
            break;
        }
    }
    if(!flag) {
        if (q < arr[0]) return p;
        else if (p > arr.back()) return q;
        else {
            if (q <= (arr[caseB] + arr[caseB+1])/2) return q;
            else if (p >= ceil(arr[caseB] + arr[caseB+1]/2.0)) return p;
            else return (arr[caseB+1] + arr[caseB])/2;
        }
    }
    int last = first;
    int result = 0;
    while (last < arr.size()-1 and arr[last+1] <= q) last++;
    if (first == 0) M.second = arr[first] - p;
    else {
        if (p >= ceil(arr[first] + arr[first-1])/2.0) M.second = arr[first] - p;
        else M = {(arr[first] + arr[first-1])/2, (arr[first] - arr[first-1])/2};
    }
    for (int i=first; i < last; i++) {
        if (M.second < (arr[i+1] - arr[i])/2) M = {(arr[i+1] + arr[i])/2, (arr[i+1] - arr[i])/2};
    }
    if (last == arr.size()-1) {
        if (M.second < q - arr[last]) M = {q, q - arr[last]};
    }
    else {
        pair<int, int> temp;
        if (q <= (arr[last+1] + arr[last])/2) temp = {q, q - arr[last]};
        else temp = {(arr[last+1] + arr[last])/2, (arr[last+1] - arr[last])/2};
        if (M.second < temp.second) M = temp;
    }
    return M.first;
}