Sort the array keeping track of indexes so I have A[0] is the index of smallest number and A[n-1] is the index of biggest number

Now if I want K-th smallest number in range [l,r] the naive way is like the code

int tmp=0;
for(int i=0;i<n;i++){
if(l<=A[i] && A[i]<=r)tmp++;
if(tmp==k){
cout<<A[i]<<endl; //output the index
break;
}
}

This has complexity O(n) for each operation

I use sqrt decompstion to make it faster