Since Ai <= 10**5, you could maintain a segment tree for each i such that it contains 1 in its jth position if arr[j] >= i.

You could form segment tree for ith index from i+1 index easily. Overall there would be total n updates. Hence O(nlogn) For querying start at root of Lth index and apply binary search to get position of kth value. O(qlogn)

AC code here