PS:
I have seen some solutions which uses two for loops to find the next right index as given in the problem.
But worst case operations will be 5*10^8 , wont the solution get TLE?

First you need to calculate the â€śPerfectArrayâ€ť. One way is to iterate from right to left while maintaining a record of where each value last appeared in the array. Then for each perfect square x in the range of [0..2\cdot 10^6], check where x - A_i last appeared and take the minimum of all these as the â€śPerfectNumberâ€ť of A_i.
To answer queries you need to count how many values in a range are > some k. This is a standard job for merge sort tree or Moâ€™s algorithm.

Itâ€™s just careless problem setting. They could have easily increased n (and decreased the limit of A_i if necessary) to prevent these solutions \mathcal{O}(n^2) solutions from passing. Even constraints are not followed (see comment by @sarthakmannahere).