#pragma once
#include <vector>
#include <iostream>
#include <random>
using namespace std;

mt19937 gen(time(0));

struct Node {
    int x, y;

    Node* left, * right;

    Node(int x) : x(x), y(gen()), left(nullptr), right(nullptr) {}

    ~Node() {
        if (left) {
            delete left;
        }
        if (right) {
            delete right;
        }
    }
};

Node* build_treap(const vector<int>& elements) {
    Node* treap = nullptr;
    vector<Node*> path_to_the_last_elem;
    for (const int elem : elements) {
        Node* current = new Node(elem);
        while (path_to_the_last_elem.size() &&
            path_to_the_last_elem.back()->y < current->y) {
            path_to_the_last_elem.pop_back();
        }
        if (path_to_the_last_elem.size()) {
            current->left = path_to_the_last_elem.back()->right;
            path_to_the_last_elem.back()->right = current;
        }
        else {
            current->left = treap;
            treap = current;
        }
        path_to_the_last_elem.push_back(current);
    }
    return treap;
}