Consider an array $a[1\ldots n]$ and another array $l = a$ (initial value). At each turn we may add next element to array $l$, or remove first element from array $l$. F.e. after first iteration it could be empty or could become $a[0, 1]$. We want to find k-th smallest element at each iteration in array $l$.
First of all if size of $l$ is less than $k$ the answer is 'No'. Let's consider more interesting case.
I've decided to have two heaps (one min and one max heap).
Max heap contains all k-th smallest elements from $a[l..r]$ and min heap contains elements which are greater than the k-th smallest element. Then answer is head of max-heap (we can take it in O(1)).
But there is a small problem. What if need to consider $a[l+1 .. r]$ (so we need to push left bound). Now of course if $r - l < k$ the answer is 'No', but what should we do otherwise? I thought we should do following: if $a[l] > maxheap$ then the answer doesn't change (because we will delete element greater than k-th smallest element), but what should we do with our heaps? Unfortunately I can't delete in heap by position (it takes a long time). The best we can do is delete root node in O(log n). How should I affect them?