template <class T>
struct node
{
  T data;
  node * left;
  node * right;
  int npl;
};

template <class T>
class leftist_tree
{
  node<T> * root;
  node<T> * merge_4_cases(node<T> *, node<T> *);
  node<T> * recursive_merge(node<T> *, node<T> *);

  void recursive_delete(node<T> * n)
  {
    if (n)
    {
      recursive_delete(n->left);
      recursive_delete(n->right);
      delete n;
    }
  }

  node<T> * recursive_copy(node<T> * n)
  {
    node<T> * copy = 0;
    if (n)
    {
      copy = new node<T>;
      copy.data = n.data;
      copy.npl = n.npl;
      copy.left = recursive_copy(n.left);
      copy.right = recursive_copy(n.right);
    }
    return copy;
  }

public:
  
  leftist_tree() : root(0) {}

  ~leftist_tree()
  {
    recursive_delete(root);
  }

  leftist_tree(const leftist_tree & t)
  {
    root = recursive_copy(t.root);
  }

  leftist_tree & operator=(const leftist_tree & t)
  {
    if (this != &t)
    {
      recursive_delete(root);
      root = recursive_copy(t.root);
    }
    return *this;
  }

  void push(const T & x)
  {
    node<T> * n = new node<T>;
    n->left = n->right = 0;
    n->data = x;
    n->npl = 0;
    root = merge_4_cases(n, root);
  }

  void pop()
  {
    node<T> * old = root;
    root = merge_4_cases(root->left, root->right);
    delete old;
  }

  const T & top()
  {
    return root->data;
  }

  bool empty()
  {
    return !root;
  }

  void merge(leftist_tree & x)
  {
    if (this != &x)
    {
      root = merge_4_cases(root, x.root);
      x.root = 0;
    }
  }
};

template <class T>
node<T> * leftist_tree<T>::merge_4_cases(node<T> * a, node<T> * b)
{
  if (!a)
    return b;
  if (!b)
    return a;
  if (a->data < b->data)
    return recursive_merge(a, b);
  else
    return recursive_merge(b, a);
}

template <class T>
node<T> * leftist_tree<T>::recursive_merge(node<T> * a, node<T> * b)
{
  if (!a->left)
    a->left = b;
  else
  {
    a->right = merge_4_cases(a->right, b);
    if (a->left->npl < a->right->npl)
      std::swap(a->left, a->right);
    a->npl = a->right->npl + 1;
  }
  return a;
}