I simply binary search on the minimum possible max that can be achieved. Similarly, I binary search on the max possible min that can be achieved.

I had a gut feeling that obtaining the minimum possible max and the maximum possible min would not interfere with each other and so the answer would just be their difference.

But I just can't prove why.