You have an array $$$arr$$$ with $$$n$$$ elements. Let number $$$i$$$ occurs in multiset $$$Q$$$ $$$arr_i$$$ times. How to get random number from multiset $$$Q$$$ faster than $$$O($$$$$$\log n$$$$$$)$$$?

$$$n$$$ <= $$$1e5$$$, $$$arr_i$$$ <= $$$1e9$$$