Implement data structure with efficient insert/findKthSmallest operations
Make an augmented search tree. This is an ordinary binary search tree, where each node additionally stores the number of elements in its subtree.  This data structure is known as order statistic tree.

If we balance the BST (making it an AVL tree for instance) then insertion can, of course, be done in logarithmic time (incrementing the node count along the search path).

Also finding the k-th element is logarithmic time. Let $n$ be the number of nodes in the left subtree of the root. If $k=n+1$ we return the root. If $k\le n$ we continue in the left subtree. If $k&gt;n$ we return the $k-(n+1)$-st node in the right subtree.