struct Node {
  Node(int i, Node *r, Node *d) : val(i), right(r), down(d) {}
  int val;
  Node *right;
  Node *down;
};
class Skiplist {
 public:
  Skiplist() {}

  bool search(int target) {
    auto cur = head;
    while (cur) {
      while (cur->right && cur->right->val < target) {
        cur = cur->right;
      }
      if (cur->right && cur->right->val == target) {
        return true;
      }
      cur = cur->down;
    }
    return false;
  }

  void add(int num) {
    int r_level = 1;
    while (r_level <= max_level && (rand() & 1 == 0)) {
      ++r_level;
    }
    if (r_level > max_level) {
      max_level = r_level;
      head = new Node(num, nullptr, head);
    }
    Node *cur = head;
    Node *last = nullptr;
    for (int l = max_level; l >= 1; --l) {
      while (cur->right && cur->right->val < num) {
        cur = cur->right;
      }
      if (l <= r_level) {
        cur->right = new Node(num, cur->right, nullptr);
        if (last) {
          last->down = cur->right;
        }
        last = cur->right;
      }
      cur = cur->down;
    }
  }

  bool erase(int num) {
    auto cur = head;
    bool seen = false;
    for (int l = max_level; l >= 1; --l) {
      while (cur->right && cur->right->val < num) {
        cur = cur->right;
      }
      if (cur->right && cur->right->val == num) {
        seen = true;
        Node *temp = cur->right;
        cur->right = cur->right->right;
        delete temp;
      }
      cur = cur->down;
    }
    return seen;
  }

 private:
  int max_level = 0;
  Node *head = nullptr;
};