/// Add / remove elements
/// No of elements < X
/// k-th smallest element
/// min / max
/// Time complexity = log(n)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
int main()
{
    /// Add elements in any random order
    pbds A;
    A.insert(11);
    A.insert(1);
    A.insert(5);
	A.insert(3);
	A.insert(7);
	A.insert(9);
	A.insert(3);

	//Total contents
	cout << "1, 3, 3 ,5, 7, 9, 11" << endl;

	//K-th smallest
	int k = 3;
	cout << k << "rd smallest: " << *A.find_by_order(k-1) << endl;

	//NO OF ELEMENTS < X
	int X = 9;

	cout << "No of elements less than " << X << " are " << A.order_of_key(X) << endl;

	//DELETE Elements
    cout << "Deleted 3" << endl;
    A.erase(A.find(3));

    //Total contents
	cout << "1, 3 ,5 ,7, 9, 11" << endl;
	
	//NO OF ELEMENTS < X
	X = 9;

	cout << "No of elements less than " << X << " are " << A.order_of_key(X) << endl;
	

	k = 3;
	cout << k << "rd smallest: " << *A.find_by_order(k-1) << endl;



	return 0;
}