I'm confused.. Why would the complexity have a factor of logAi in the "Bonus" part. I can only think of a O(q*log^3 n) solution. Binary search over the array ~~segment ~~and find the value that has k-1 smaller numbers in O(log^2 n).
Also, would appreciate if you could upvote me. Need karma points :P
Thanks!