#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cmath>
#include <utility>
#include <random>

void doOnStart() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
#ifdef _offline
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

struct Node {
public:
    int key;
    int maxHeight = 0;
    Node* left = nullptr;
    Node* right = nullptr;
    Node* parent = nullptr;

    Node() = default;

    explicit Node(int key) : key(key) {
    }

    ~Node() {
        if (left != nullptr) {
            delete left;
        }
        if (right != nullptr) {
            delete right;
        }
    }
};

class SplayTree {
public:
    SplayTree() = default;

    ~SplayTree() {
        delete root_;
    }

    void insert(int key) {
        if (root_ == nullptr) {
            root_ = new Node(key);
            root_->maxHeight = 1;
            return;
        }
        if (find(key) == nullptr) {
            std::pair<Node*, Node*> trees = split(key);
            Node* new_node = new Node(key);
            new_node->left = trees.first;
            new_node->right = trees.second;
            new_node->maxHeight = max(new_node->left, new_node->right) + 1;
            if (new_node->left != nullptr) {
                new_node->left->parent = new_node;
            }
            if (new_node->right != nullptr) {
                new_node->right->parent = new_node;
            }
            root_ = new_node;
        }
    }

    Node* find(int key) {
        Node* result = goDown(root_, key);
        splay(result);
        return result->key == key ? result : nullptr;
    }

    int splay(Node* node) {
        int count = 0;
        while (node->parent != nullptr) {
            Node* parent = node->parent;
            if (parent->left == node) {
                if (parent->parent == nullptr) {
                    zig(node->parent);
                } else if (parent->parent->left == parent) {
                    zig(parent->parent);
                    zig(parent);
                } else {
                    zig(parent);
                    zag(parent);
                }
            } else {
                if (parent->parent == nullptr) {
                    zag(node->parent);
                } else if (parent->parent->left == parent) {
                    zag(parent->parent);
                    zag(parent);
                } else {
                    zag(parent);
                    zig(parent);
                }
            }
            count++;
        }
        return count;
    }

    int getHeight() const {
        return root_->maxHeight;
    }

private:
    Node* root_;

    void zag(Node* node) {
        Node* parent = node->parent;
        Node* right = node->right;
        if (right == nullptr) {
            return;
        }
        if (parent != nullptr) {
            if (parent->left == node) {
                parent->left = right;
            } else {
                parent->right = right;
            }
        }
        Node* tmp = right->left;
        right->left = node;
        node->right = tmp;

        right->parent = parent;
        node->parent = right;
        if (tmp != nullptr) {
            tmp->parent = node;
        }

        node->maxHeight = max(node->left, node->right) + 1;
        right->maxHeight = max(right->left, right->right) + 1;
    }

    void zig(Node* node) {
        Node* parent = node->parent;
        Node* left = node->left;
        if (left == nullptr) {
            return;
        }
        if (parent != nullptr) {
            if (parent->left == node) {
                parent->left = left;
            } else {
                parent->right = left;
            }
        }
        Node* tmp = left->right;
        left->right = node;
        node->left = tmp;

        left->parent = parent;
        node->parent = left;
        if (tmp != nullptr) {
            tmp->parent = node;
        }

        node->maxHeight = max(node->left, node->right) + 1;
        left->maxHeight = max(left->left, left->right) + 1;
    }

    Node* goDown(Node* current, int key) const {
        if (current == nullptr) {
            return nullptr;
        }
        if (current->key == key || (current->left == nullptr && current->right == nullptr)) {
            return current;
        }
        if (key < current->key) {
            return goDown(current->left, key);
        } else {
            return goDown(current->right, key);
        }
    }

    std::pair<Node*, Node*> split(int key) {
        splay(goDown(root_, key));
        if (key <= root_->key) {
            Node* left = root_->left;
            root_->left = nullptr;
            return {left, root_};
        } else {
            Node* right = root_->right;
            root_->right = nullptr;
            return {root_, right};
        }
    }

    void merge(Node* left, Node* right) {
        Node* max_left = maxNode(left);
        splay(max_left);
        max_left->right = right;
    }

    Node* maxNode(Node* current) {
        if (current->right == nullptr) {
            return current;
        }
        return maxNode(current->right);
    }

    int max(Node* node_left, Node* node_right) {
        if (node_left == nullptr) {
            if (node_right == nullptr) {
                return 0;
            } else {
                return node_right->maxHeight;
            }
        } else {
            if (node_right == nullptr) {
                return node_left->maxHeight;
            } else {
                return std::max(node_left->maxHeight, node_right->maxHeight);
            }
        }
    }
};

signed main() {
    doOnStart();
    SplayTree tree = SplayTree();
    tree.insert(1);
    tree.insert(4);
    Node* e = tree.find(1);
    std::cout << e->maxHeight << '\n';
    return 0;
}