#include #include using namespace std; template class node { public: node(T key, node* parent, node* right, node* left) : _key{key}, _parent{parent}, _right{right}, _left{left} {} T& key() { return _key; } const T& key() const { return _key; } node*& parent() { return _parent; } const node*& parent() const { return _parent; } node*& right() { return _right; } const node*& right() const { return _right; } node*& left() { return _left; } const node*& left() const { return _left; } private: T _key; node* _parent; node* _right; node* _left; }; class bst { public: bst() : _duplicates{0}, _root{nullptr} {} bst* add(int val) { node* iter = _root; node* prev = nullptr; while(iter) { prev = iter; if(iter->key() == val) { _duplicates++; return this; } if(iter->key() > val) iter = iter->right(); else iter = iter->left(); } node* nodus = new node{val, prev, nullptr, nullptr}; if(!prev) _root = nodus; else if(prev->key() > val) prev->right() = nodus; else prev->left() = nodus; return this; } const int& duplicates() const { return _duplicates; } private: int _duplicates; node* _root; }; int main() { ifstream in("input.txt"); ofstream out("output.txt"); for(int ts = 0; ts < 100; ++ts) { bst* b = new bst{}; int n; in >> n; int e; for(int i = 0; i < n; ++i) { in >> e; b->add(e); } out << b->duplicates() << endl; } in.close(); out.close(); return 0; }