Для начала рекомендую переотправить решение, таймауты могут случаться просто из-за всплеска нагрузки на тестирующий сервер.
Если это не поможет, то вам действительно стоит оптимизировать print, потому что в Python очень дорогие вызовы функций, на моём компьютере вот такие замеры получились:
l = list(range(10**5))
for i in l: # 107 ms
print(i, end=' ')
s = ' '.join(map(str, l))
print(s) # 55 ms
В целом при отладке таких проблем имеет смысл искать крайние случаи, на которых ваша программа будет работать медленнее всего — в данном случае, если я правильно понял вашу программу (читал не очень внимательно), это упорядоченный в обратном порядке массив размером 10^5.
UPD: Я нашёл плохой вход для вашей программы - проверьте её на массиве, где все значения одинаковые, время выполнения получилось около 20 секунд на массиве длиной 10^4, на 10^5 ответа я не дождался.
Это происходит вот из-за этих строк:
for i in range(n):
left = 1
right = l
...
elif x[m[mid]] == x[i]:
left += 1
...
В худшем случае у вас здесь возникает O(n^2).
Кажется, достаточно будет просто поменять цикл на вот такой:
for i in range(n):
left = 1
right = l
while left <= right:
mid = (left+right) // 2
if x[m[mid]] <= x[i]:
left = mid+1
else:
right = mid-1
...
