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

mt19937 gen(time(0));

struct Node {
    int x, size, maximum;

    Node* left, * right;

    Node(int x)
        : x(x)
        , size(1)
        , maximum(x)
        , left(nullptr)
        , right(nullptr) {
    }

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


int node_size(Node* t) {
    if (t == nullptr) {
        return 0;
    }
    return t->size;
}


int node_maximum(Node* t) {
    if (t == nullptr) {
        return INT_MIN;
    }
    return t->maximum;
}


void update(Node* t) {
    if (t == nullptr) {
        return;
    }
    t->size = node_size(t->left) + node_size(t->right) + 1;
    t->maximum = max(node_maximum(t->left), max(t->x, node_maximum(t->right)));
}




Node* merge(Node* l, Node* r) {
    if (l == nullptr) {
        return r;
    }
    if (r == nullptr) {
        return l;
    }
    // if (l->y > r->y) {
    int val = gen() % (l->size + r->size);
    if (val < l->size) {
        l->right = merge(l->right, r);
        update(l);
        return l;
    }
    else {
        r->left = merge(l, r->left);
        update(r);
        return r;
    }
}




pair<Node*, Node*> split_size(Node* t, int ind) {
    // Делим элементы t на два дерева так, чтобы в первом дереве было
    // ind элементов, а во втором --- все остальные.
    // 
    // Если в t меньше ind элементов, то все элементы будут в первом
    // дереве, а второе будет пустым.
    if (t == nullptr) {
        return { nullptr, nullptr };
    }
    if (node_size(t->left) < ind) {
        auto split_right = split_size(t->right, ind - node_size(t->left) - 1);
        t->right = split_right.first;
        update(t);
        return { t, split_right.second };
    }
    else {
        auto split_left = split_size(t->left, ind);
        t->left = split_left.second;
        update(t);
        return { split_left.first, t };
    }
}




Node* insert(Node* t, int ind, int x) {
    auto split_tree = split_size(t, ind);
    return merge(merge(split_tree.first, new Node(x)),
        split_tree.second);
}




Node* remove(Node* t, int ind) {
    auto split_tree = split_size(t, ind + 1);
    auto split_left = split_size(split_tree.first, ind);
    delete split_left.second;
    return merge(split_left.first, split_tree.second);
}


int at(Node* t, int ind) {
    if (t == nullptr) {
        return -1;
    }
    if (node_size(t->left) == ind) {
        return t->x;
    }
    if (node_size(t->left) < ind) {
        return at(t->right, ind - node_size(t->left) - 1);
    }
    else {
        return at(t->left, ind);
    }
}



int maximum(Node*& t, int l, int r) {
    // Максимум на интервале [l, r), l < r
    auto split_tree = split_size(t, l);
    auto split_right = split_size(split_tree.second, r - l);
    int result = split_right.first->maximum;
    t = merge(split_tree.first, merge(split_right.first, split_right.second));
    return result;
}





void print_node(Node* t) {
    cout << t->x << '|' << t->size;
}

void print_treap_recursive(Node* t) {
    if (t == nullptr) {
        return;
    }
    cout << "(";
    print_treap_recursive(t->left);
    print_node(t);
    print_treap_recursive(t->right);
    cout << ")";
}

void print_treap_recursive_with_depth(Node* t, int depth) {
    if (t == nullptr) {
        return;
    }
    print_treap_recursive_with_depth(t->left, depth + 1);
    for (int i = 0; i < depth; ++i) {
        cout << ".";
    }
    print_node(t);
    cout << '\n';
    print_treap_recursive_with_depth(t->right, depth + 1);
}

void print_treap(Node* root) {
    print_treap_recursive(root);
    cout << '\n';
}


void print_treap_with_depth(Node* root) {
    print_treap_recursive_with_depth(root, 0);
    cout << '\n';
}