// partition with a BST

typedef int size_t;

template <class Item, class Key>
class ST {

  struct node {
    Item item; node* l; node* r; size_t N;
    node(Item x) { item = x; l = 0; r = 0; }
  } ;

  typedef node* link;

private:

  link head;

  void partR(link h, int k) {
    int t = (h->l == 0) ? 0 : h->l->N;
    if (t > k) { partR(h->l, k); rotR(h); }
    if (t < k) { partR(h->r, k-t-1); rotL(h); }
  }

public:

  void part(int k) { partR(head, k); return; }

};