public static int sherlockAndMinimax(List<Integer> arr, int p, int q) {
        //I need a sorted set, and in this sorted set: higher() and lower() functions are very useful
        TreeSet<Integer> tree = new TreeSet<Integer>(arr);
        //If p is upper bound or q is lower bound we are ready, so I made cases: 
        int output = 0;
        if (q <= tree.first()) {
            output = tree.first();
        } else if(p >= tree.last()) {
            output = tree.last();
        /*here: we have element(s) between p and q
        these elements generates intervals; I need the widest interval, so I compare them
        but be careful, we have to add one new interval before the first one end one after the least one*/
        } else {
            int start = 0;
            int end = 0;
            if(tree.contains(p) || tree.higher(p) == null) {
                start = p;
                //this is the start of the added new "before" interval:
            } else {
                start = 2 * p - tree.higher(p);
            }
            if(tree.contains(q) || tree.lower(q) == null) {
                end = q;
            } else {
                //this is the end of the added new "after" interval:
                end = 2 * q - tree.lower(q);
            }
            int i = start;
            //width:
            int maxDiff = 0;
            //center of the actual best interval:
            int middle = 0;
            tree.add(end);
            while(i <= end) {
                if(tree.higher(i) != null) {
                    int actDiff = (tree.higher(i) - i) / 2;
                    //comparison of the widths:
                    if (actDiff > maxDiff && (tree.higher(i) + i) / 2 <= q) {
                        maxDiff = actDiff;
                        middle = (tree.higher(i) + i) / 2;
                    }
                    i = tree.higher(i);
                } else {
                    break;
                }                
            }
            output = middle;
        }
        return output;
    }