You can use coordinate compression. Make a copy of array a, let's call it d, sort it, delete all unique elements, and make every element in a equal to the index of that element in sorted array(you can use std::lower_bound).

Now you have number <= 1e5, you can make an array instead of map, and avoid additional log (don't forget that you need to do occurences[x] == d[x] now)