Algorithm Improvement - element differences in list
One simple observation is that this problem gets much easier if you sort nums O(n log(n). Then you can use bisect_left which uses binary search to find where an element would go in a sorted list and is O(log(n)) for each element in m. This yields a total time of O((n+m) log(n))

from bisect import bisect_left

def sol_sorted(nums,maxes):
    output = []
    nums.sort()
    for m in maxes:
        ind = bisect_left(nums, m)
        output.append(len(nums) - ind)
    return output