Problem - Kth Number in Range

Given an array, answer queries: "What is the $k$-th smallest element in subarray $[l, r]$?" Example: $A = [1, 5, 2, 6, 3, 7, 4]$ Query $(2, 5, 3)$: 3rd smallest in $[2, 6, 3, 7]$ is $6$.

This is solvable with wavelet trees, but persistent segment tree gives a clean solution. Build persistent segment tree on coordinate-compressed values.

Version $i$ contains elements $A[0..i-1]$. Constraints: up to $10^5$ elements and queries.