#include <iostream>
#include <random>

struct Node {
  int priority;
  int value;
  Node* left;
  Node* right;

  Node(int value, std::mt19937& gen) : value(value), left(nullptr), right(nullptr) {
    priority = gen();
  }
};

struct SplitResult {
  Node* left;
  Node* right;
};

class Treap {
  Node* Merge(Node* left, Node* right);
  SplitResult Split(Node* tree, int value);
  Node* FindMin(Node* root, int);
  Node* Find(Node* root, int key);
public:
  Node* Insert(Node* tree, Node* to_insert);
  void Erase(Node* tree, int to_erase);
  void Delete(Node* tree);
  void Print(Node* tree);
};

Node* Treap::Find(Node* root, int key) {
  if (root->value == key) return root;
  if (root->value > key) return Find(root->left, key);
  return Find(root->right, key);
}

Node* Treap::FindMin(Node* root, int key) {
  if (root->left == nullptr) return root;
  if (root->left->value > key) {
    FindMin(root->left, key);
  }
  return root;
}

Node* Treap::Merge(Node* left, Node* right) {
  if (right == nullptr) {
    return left;
  }
  if (left == nullptr) {
    return right;
  }
  if (left->priority > right->priority) {
    left->right = Merge(left->right, right);
    return left;
  }
  right->left = Merge(left, right->left);
  return right;
}

SplitResult Treap::Split(Node* tree, int value) {
  if (tree == nullptr) {
    return SplitResult{nullptr, nullptr};
  }
  if (value > tree->value) {
    SplitResult result = Split(tree->right, value);
    tree->right = result.left;
    return {tree, result.right};
  }
  SplitResult result = Split(tree->left, value);
  tree->left = result.right;
  return {result.left, tree};
}

Node* Treap::Insert(Node* tree, Node* to_insert) {
  SplitResult result = Split(tree, to_insert->value);
  Node* tmp = Merge(result.left, to_insert);
  Node* tmp2 = Merge(tmp, result.right);
  return tmp2;
}

void Treap::Erase(Node* tree, int key) {
  Node* to_erase = Find(tree, key);
  if (to_erase == nullptr) return;
  SplitResult result = Split(tree, to_erase->value);
  Node* parent = FindMin(result.right, to_erase->value);
  SplitResult result_right = Split(result.right, parent->value);
  delete result_right.left;
  Merge(result.left, result_right.right);
}

void Treap::Delete(Node* tree) {
  if(tree != nullptr) {
    Delete(tree->left);
    Delete(tree->right);
    delete tree;
  }
}

void Treap::Print(Node* tree) {
  if(tree != nullptr) {
    Print(tree->left);
    std::cout << "value: " << tree->value << "pr: " << tree->priority << '\n';
    Print(tree->right);
  }
}

int main() {
  Treap treap;
  std::mt19937 gen;

  Node* root = nullptr;

  int value;
  int node_value = 5;

// 3 5 4 2 1
// 3: -795755684
// 5:  581869302
// 4: -404620562
// 2: -708652711
// 1:  545404204
  while (node_value-- > 0) {
    std::cin >> value;
    Node* new_node = new Node(value, gen);
    root = treap.Insert(root, new_node);
  }

  treap.Erase(root, 5);

  std::cout << root->value << '\n';

  treap.Print(root);

  treap.Delete(root);
}