Untitled

#include "iostream"
#include <map>

using namespace std;

template<typename T>
class BinarySearchTree {
private:
    BinarySearchTree<T>* left{nullptr};
    BinarySearchTree<T>* right{nullptr};
    static map<int, int> val_to_i;
public:
    T value;
    int index;

    explicit BinarySearchTree(T value) {
        this->value = value;
    }

    void insert(T new_value) {
        bool left_tr = false;
        BinarySearchTree<T>* prev = nullptr;
        BinarySearchTree<T>* current = this;
        while(current != nullptr) {
            prev = current;
            if(new_value < current->value) {
                current = current->left;
                left_tr = true;
            } else {
                current = current->right;
                left_tr = false;
            }
        }
        if (left_tr) {
            prev->left = new BinarySearchTree<T>(new_value);
        } else {
            prev->right = new BinarySearchTree<T>(new_value);
        }
    }

    static int count(BinarySearchTree* tree) {
        if (tree == nullptr) {
            return 0;
        }
        if(tree->left == nullptr && tree->right == nullptr) {
            BinarySearchTree<T>::val_to_i[tree->value] = 1;
            return 1;
        }
        if(BinarySearchTree<T>::val_to_i.find(tree->value) == BinarySearchTree<T>::val_to_i.end()) {
            auto res = 1 + count(tree->left) + count(tree->right);
            BinarySearchTree<T>::val_to_i[tree->value] = res;
            return res;
        } else {
            return BinarySearchTree<T>::val_to_i[tree->value];
        }
    }

    static void print(BinarySearchTree<T>* tree, int curr_i) {
        int li, l_count, ri;

        if (tree->left != nullptr) {
            l_count = BinarySearchTree<T>::val_to_i[tree->left->value];
            li = curr_i + 1;
        } else {
            li = -1;
            l_count = 0;
        }
        if (tree->right != nullptr) {
            ri = l_count + curr_i + 1;
        } else {
            ri = -1;
        }
        cout << tree->value << ' ' << li << ' ' << ri << endl;
        if (tree->left != nullptr) {
            print(tree->left, li);
        }
        if (tree->right != nullptr) {
            print(tree->right, ri);
        }
//        int iter_index = st_index;
//        int li, ri;
//
//        if (left != nullptr) {
//            li = iter_index+1;
//            iter_index = left->print(li);
//        } else {
//            li = -1;
//        }
//        if (right != nullptr) {
//            ri = iter_index+1;
//            iter_index = right->print(ri);
//        } else {
//            ri = -1;
//        }
//        cout << value << ' ' << li << ' ' << ri << endl;
//        return iter_index;
    }
};

//template<typename T>
//class BinarySearchTreeArray {
//private:
//    T* arr;
//    int size;
//
//    explicit BinarySearchTreeArray(int size) {
//        arr = new T[size];
//        this->size = size;
//    }
//    T* left(int i) {
//        return arr[2*i + 1]
//    };
//    T* right(int i) {
//        return arr[2*i + 2];
//    };
//    void insert(T new_value) {
//        bool left_tr = false;
//        int prev_i = -1;
//        int current_i = 0;
//        while(arr[current_i] != nullptr) {
//            prev_i = current_i;
//            if(new_value < arr[current_i]) {
//                current_i = left(current_i);
//                left_tr = true;
//            } else {
//                current_i = right(current_i);
//                left_tr = false;
//            }
//        }
//        if (left_tr) {
//            arr[left(prev_i)] = new_value;
//        } else {
//            arr[right(prev_i)] = new_value;
//        }
//    }
//
//    void print() {
//        for (int i = 0; i < size; i++) {
//            if
//        }
//    }
//};

template<>
map<int, int> BinarySearchTree<int>::val_to_i{};

int main() {
    int n;
    cin >> n;
    int* arr = new int[n];
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    int temp;
    auto tree = BinarySearchTree<int>(arr[0]);

    for (int i = 1; i < n; i++) {
        tree.insert(arr[i]);
    }

    cout << n << endl;
    BinarySearchTree<int>::count(&tree);
    BinarySearchTree<int>::print(&tree, 1);
    cout << 1 << endl;
    return 0;
}

//int main() {
//    int n;
//    cin >> n;
//    int* arr = new int[n];
//    for (int i = 0; i < n; i++) {
//        cin >> arr[i];
//    }
//
//    int temp;
//    auto tree = BinarySearchTree<int>(100001);
//
//    for (int i = 0; i < n; i++) {
//        tree.insert(arr[i]);
//    }
//
//    cout << n << endl;
//
//    cout << tree.print(1) << endl;
//    return 0;
//}