2819. Minimum Relative Loss After Buying Chocolates

First sort prices.

For one query, imagine mi is 1. It can be shown that Bob should select either the first one (the cheapest one) or the last one (the most expensive).

Now if mi > 1, separate the chocolates into two parts. The first part is chocolates having a price less than or equal to k, the rest would be in the second part.

Knowing how many chocolates Bob should pick from the first part is sufficient. Of course, Bob should select a prefix from this part and a suffix from the second part.

To find the number of chocolates from the first part, do a binary search on the first part.