template<typename K>

class splaytree {
 private:
  struct node {

    K key; int size;
    node *l, *r, *p;

    node() { size=0; }
    node (K _key) { key=_key; size=1; }

    void update() { size = 1 + l->size + r->size; }
  } *root, *NIL;

  void clear (node *u) {
    if (u == NIL) return;

    clear (u->l); clear (u->r);

    delete u;
  }

  // rotate edge x - x's parent
  void rotate (node *u) {

    node *v = u->p, *w = v->p;

    if (u == v->l) {
      v->l = u->r;

      if (u->r != NIL) u->r->p = v;

      u->r = v;
      v->p = u;
    } else {

      v->r = u->l;
      if (u->l != NIL) u->l->p = v;

      u->l = v;
      v->p = u;
    }

    u->p = w;
    if (w != NIL) {

      if (w->l == v) w->l = u;

      else           w->r = u;
    }

    v->update();

    u->update();
  }

  node* splay (node *u) {

    if (u == NIL) return NIL;
    while (u->p != NIL) {

      node *v = u->p, *w = v->p;

      if (w == NIL) {
    // zig
  rotate (u);

    break;
      }
      if ((v->l == w) == (w->l == v)) {

    // zig-zig
  rotate (v);
  rotate (u);
      } else {

    // zig-zag
  rotate (u);
  rotate (u);
      }
    }
    return u;
  }

  node* splay (node *u, K key) {

    node *v=u;
    while (v != NIL && v->key != key) {

      node *w = (key < v->key) ? v->l : v->r;

      if (w == NIL) break;
      v = w;
    }

    return splay (v);
  }

  node* insert (node *u, K key) {

    node *v = u, *w = NIL, *x = new node (key); x->l=x->r=x->p=NIL;

    while (v != NIL) {
      w = v;
      ++v->size;

      if (key < v->key) v = v->l; else v = v->r;
    }

    x->p = w;
    if (w != NIL) {

      if (key < w->key) w->l = x; else w->r = x;
    }

    return splay (x);
  }

  node* join (node *u, node *v) {

    if (u != NIL) u->p = NIL;

    if (v != NIL) v->p = NIL;

    if (u == NIL) return v;
    if (v == NIL) return u;

    while (u->r != NIL) u=u->r;

    splay (u);
    u->r = v;

    v->p = u;
    u->update();
    return u;
  }

  node* remove (node *u) {
    splay (u);

    node *v = join (u->l, u->r);

    delete u;
    return v;
  }

 public:

  splaytree()  { NIL=new node(); NIL->p=NIL->l=NIL->r=NIL; root=NIL; }
  ~splaytree() { clear (root); delete NIL; }

  void clear() { clear (root); root=NIL; }

  int  size()  { return root->size;      }
  void insert (K key) { root = insert (root, key); }

  bool find (K key)   { root = splay (root, key); return (key == root->key); } 
};