k-th smallest element in sliding segment
Maintain an AVL tree $B$ that stores the elements in $l$.
In addition, for each element $a$ in $l$, keep a pointer $p_a$ to the corresponding node in $B$.

When an element $x$ is added to $l$, then simply insert a new node $v$ representing $x$ into $B$ and make $p_x$ point to $v$.

When the first element $y$ of $l$ needs to be removed, delete (the node pointed by) $p_y$ from $B$.

To report the $k$-minimum element in $l$, simply look for the minimum element in $B$ (i.e., the one stored in the leftmost node). This can be done in $O(\log n)$ time by just keeping, in each node $v$, the size of the subtree of $B$ rooted in $v$.


By combining the above operations, each turn of your problem will require $O(\log(1 + |l|)) = O(\log n)$ time.