Curator Sona freezes a new sorted-value snapshot after each crystal is added. For every historical range, answer its k-th smallest crystal without rebuilding the archive. Input: n q; n values; q triples l r k (1-based inclusive range and rank). Output the k-th smallest value in each range.
Example 1:
Example 2:
Example 3:
Constraints:
1≤n,q≤200000; |value|≤10^9; 1≤k≤r-l+1.
Tags:
