template<class T, class U, class TCmp, class UCmp>
void Treap<T, U, TCmp, UCmp>::Insert(const T& key, const U& priority) {
  TUNode* cur = dynamic_cast<TUNode*>(root_);
  TUNode* parent_of_cur = nullptr;

  // false - left.
  bool last_move = false;

  while (cur != nullptr && !cmp_u_(cur->priority, priority)) {
    // If we are less than need.
    parent_of_cur = cur;
    if (cmp_t_(cur->key, key)) {
      cur = dynamic_cast<TUNode*>(cur->right);
      last_move = true;
    } else {
      cur = dynamic_cast<TUNode*>(cur->left);
      last_move = false;
    }
  }

  // If the treap is empty
  if (cur == nullptr && parent_of_cur == nullptr) {
    root_ = new TUNode(key, priority);
    return;
  }

  // If cur is a leaf, just push.
  if (cur == nullptr) {
    (last_move ? parent_of_cur->right : parent_of_cur->left) =
        new TUNode(key, priority);
    return;
  }

  TUNode* left = nullptr;
  TUNode* right = nullptr;
  Split(left, right, cur, key);

  TUNode* new_elem = new TUNode(key, priority);

  new_elem->left = dynamic_cast<BinNode*>(left);
  new_elem->right = dynamic_cast<BinNode*>(right);

  if (parent_of_cur == nullptr) {
    root_ = new TUNode(key, priority);

    dynamic_cast<TUNode*>(root_)->left = left;
    dynamic_cast<TUNode*>(root_)->right = right;

    return;
  }

  (last_move ? parent_of_cur->right : parent_of_cur->left) =
    dynamic_cast<BinNode*>(new_elem);
}