You don't need to compute ahead that way. Even so, I'm able to tweak your code to pass. I don't think it SHOULD pass though - with all the repeated sorting/set conversion, and the magic number you have there. As part of my modification, I set it to 600_000. Maybe it doesn't need to be quite as high but uhm. Probably not much lower either. Unless of course you were to hard-code that specific test which is the only one with a large n. I wouldn't call that cheating but I wouldn't call it solving it either.

if you mean that you sort repeatedly, then that ought to be bit of a red flag

it may be helpful to do this with pen and paper, the human brain tends to optimize tasks it carries out

we are supposed to crete an array u which has the mentioned sequence in ascending order. for the return part, given input is an index and its supposed to return the element from that index in the array.
This is my understanding.
I'm able to run my solution in difference compiler (programmiz) and get correct output for all the mentioned tests, however it's getting timed out here

Thanks a lot for this comment. really helped me to find the issue after busting my head for hours.