<p>Given an integer array <code>nums</code>, return <code>true</code> if any value appears <strong>at least twice</strong> in the array, and return <code>false</code> if every element is distinct.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,2,3,1]</span></p>

<p><strong>Output:</strong> <span class="example-io">true</span></p>

<p><strong>Explanation:</strong></p>

<p>The element 1 occurs at the indices 0 and 3.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,2,3,4]</span></p>

<p><strong>Output:</strong> <span class="example-io">false</span></p>

<p><strong>Explanation:</strong></p>

<p>All elements are distinct.</p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,1,1,3,3,4,3,2,4,2]</span></p>

<p><strong>Output:</strong> <span class="example-io">true</span></p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution {
public:
template<typename T>
struct Tr_Nd {
	T key; int height, count, size; Tr_Nd* left; Tr_Nd* right; Tr_Nd* par = nullptr;
	Tr_Nd(T x) : key(x), left(nullptr), right(nullptr), height(1), count(0), size(1) {}
};
template<typename T>
class AVL {
private:
	int Gt_Ht(Tr_Nd<T>* N) { return N ? N->height : 0; }
	int Gt_Blnc(Tr_Nd<T>* N){ return N ? Gt_Ht(N->left) - Gt_Ht(N->right) : 0;}
	void Update(Tr_Nd<T>* N) { if (N) { N->height = 1 + max(Gt_Ht(N->left), Gt_Ht(N->right));
		N->size = 1 + Gt_Sz(N->left) + Gt_Sz(N->right);
	} }
	Tr_Nd<T>* R_Rot(Tr_Nd<T>* y) { if(!y || !y->left) return y; Tr_Nd<T>* x = y->left; Tr_Nd<T>* T2 = x->right;
		x->right = y; y->left = T2; if(T2) T2->par = y; x->par = y->par; y->par = x; Update(y); Update(x); return x;
	}
	Tr_Nd<T>* L_Rot(Tr_Nd<T>* x) { if(!x || !x->right) return x; Tr_Nd<T>* y = x->right; Tr_Nd<T>* T2 = y->left;
		y->left = x; x->right = T2; if(T2) T2->par = x; y->par = x->par; x->par = y; Update(x); Update(y); return y;
	}
public:
	int Gt_Sz(Tr_Nd<T>* N) { return N ? N->size : 0; }
	Tr_Nd<T>* BN(Tr_Nd<T>* N, T key) { Update(N); int balance = Gt_Blnc(N);
		if (balance > 1) { if (key < N->left->key) { return R_Rot(N);
		} else { N->left = L_Rot(N->left); return R_Rot(N); }
		} else if (balance < -1) { if (key > N->right->key) { return L_Rot(N);
		} else { N->right = R_Rot(N->right); return L_Rot(N);}}return N; 
	}
	Tr_Nd<T>* BND(Tr_Nd<T>* N) { Update(N); int balance = Gt_Blnc(N);
		if (balance > 1) { if (Gt_Blnc(N->left) < 0) N->left = L_Rot(N->left);
		return R_Rot(N); } if (balance < -1) { if (Gt_Blnc(N->right) > 0) N->right = R_Rot(N->right);
		return L_Rot(N); } return N;
	}
};
template<typename T>
class aset {
private:
	Tr_Nd<T>* Rt; AVL<T> z;
	int cnt = 0; T first = numeric_limits<T>::max(); T last = numeric_limits<T>::min();
	Tr_Nd<T>* insert(Tr_Nd<T>* N, T key, Tr_Nd<T>*& n = nullptr, Tr_Nd<T>* par = nullptr) { if (N == nullptr) {
    	cnt++; first = min<T>(first, key); last = max<T>(last, key); n = new Tr_Nd<T>(key); n->par = par; return n;}
        if (key < N->key) N->left = insert(N->left, key, n, N);
        else if (key > N->key) N->right = insert(N->right, key, n, N);
        else { return n = N; }
        return z.BN(N, key);
    }
	Tr_Nd<T>* Mn_Vl_Nd(Tr_Nd<T>* N) { while (N && N->left != nullptr) N = N->left; return N; }
	Tr_Nd<T>* Dlt_Nd(Tr_Nd<T>* Rt, T key) { if (Rt == nullptr) return Rt;
		if (key < Rt->key) Rt->left = Dlt_Nd(Rt->left, key);
		else if (key > Rt->key) Rt->right = Dlt_Nd(Rt->right, key);
		else {if (Rt->left == nullptr || Rt->right == nullptr) {
				Tr_Nd<T>* Tm = Rt->left ? Rt->left : Rt->right;
				if (Tm == nullptr) {Tm = Rt; Rt = nullptr;}
				else { *Rt = *Tm; } delete Tm; cnt--;}
			else {
				Tr_Nd<T>* Tm = Mn_Vl_Nd(Rt->right); Rt->key = Tm->key; Rt->count = Tm->count; 
				Rt->size = Tm->size; Rt->right = Dlt_Nd(Rt->right, Tm->key);}
				if(Rt->right) Rt->right->par = Rt;
		} if (Rt == nullptr) return Rt; return z.BND(Rt);
	}
	void Upd_F() { first = Mn_Vl_Nd(Rt)->key; }
	void Upd_L() { Tr_Nd<T>* cur = Rt; while (cur && cur->right != nullptr) cur = cur->right; last = cur->key; }
	Tr_Nd<T>* FBO(Tr_Nd<T>* N, int ord) { if (N == nullptr || ord <= 0 || ord > z.Gt_Sz(N)) return nullptr;
        int leftt_count = z.Gt_Sz(N->left); if (ord <= leftt_count) return FBO(N->left, ord);
        if (ord <= leftt_count + 1) return N; return FBO(N->right, ord - leftt_count - 1);
    }
    int OOK(Tr_Nd<T>* N, T key) { if (N == nullptr) return 0;
        if (key < N->key) return OOK(N->left, key);
        else if (key > N->key) return z.Gt_Sz(N->left) + 1 + OOK(N->right, key); else return z.Gt_Sz(N->left);
    } //left swap right and '<' swap '>' for greater equal
public:
	aset() : Rt(nullptr) {}
	class Iterate {
    private: Tr_Nd<T>* Cur; aset<T>* tree;
        Tr_Nd<T>* find_next(Tr_Nd<T>* N) { if (N->right != nullptr) return tree->Mn_Vl_Nd(N->right);
            Tr_Nd<T>* Par = N->par; while (Par && N == Par->right) { N = Par; Par = Par->par;} return Par;
        }
    public:
        Iterate(Tr_Nd<T>* Rt, aset<T>* tree) : Cur(Rt ? tree->Mn_Vl_Nd(Rt) : nullptr), tree(tree) {}
        bool operator!=(const Iterate& other) const { return Cur != other.Cur; }
        pair<const T, int&> operator*() const { return {Cur->key, Cur->count}; }
    	pair<const T, int&>* operator->() const { return new pair<const T, int&>(Cur->key, Cur->count); }
        Iterate& operator++() { if (Cur != nullptr) Cur = find_next(Cur); return *this;}
		Iterate operator++(int) { if (Cur != nullptr) Cur = find_next(Cur); return *this; }
		Iterate operator+(size_t n) const { Iterate it = *this; for (size_t i = 0; i < n && it.Cur; ++i) ++it; return it;}
		Iterate operator-(size_t n) const { Iterate it = *this; for (size_t i = 0; i < n && it.Cur; ++i) --it; return it;}
		friend class aset<T>;
    };
    Iterate begin() { return Iterate(Rt, this); }
    Iterate end() { return Iterate(nullptr, this); }
	void insert(T key) { Rt = insert(Rt, key);}
	void erase(T key) { Rt = Dlt_Nd(Rt, key); if(cnt == 0){first = numeric_limits<T>::max(); last = numeric_limits<T>::min();}
		else{ if(first == key) Upd_F(); if(last == key) Upd_L();} }
	bool find(T key) const{ return Search(Rt, key) == nullptr ? false : true; }
    int size() const { return cnt; }
    T front() const{ return first; }
    T back() const{ return last; }
    auto find_by_order(int ord){ return FBO(Rt, ord);}
    int order_of_key(T key) { return OOK(Rt, key);}
	int& operator[](T key) { Tr_Nd<T>* N; Rt = insert(Rt, key, N); return N->count; }
};
    bool containsDuplicate(vector<int>& ar) {
        aset<int> m;
        for(auto i : ar) {
            m[i]++;
        }
        for(auto [a, b] : m) if(b > 1) return true;
        return false;
    }
};
72078