#include<bits/stdc++.h>

namespace AVL
{
	template<class T> class multiset
	{
    	class node
    	{
        	friend class multiset; T key; size_t count, height; node *left, *right;

        	node(const T x) : key(x), count(1), height(1), left(nullptr), right(nullptr) {}

        	friend size_t Height(const node* t)
        	{
            	return t?t->height:0;
        	}

        	node* update_height()
        	{
            	height = std::max(Height(left),Height(right))+1; return this;
        	}

        	int Balance() const
        	{
            	return int(Height(left))-int(Height(right));
        	}

        	friend node* rotate_right_aux(node* y)
        	{
            	node *x = y->left, *z = x->right;

            	x->right = y, y->left = z, y->update_height();

            	return x->update_height();
        	}

        	friend node* rotate_left_aux(node* x)
        	{
            	node *y = x->right, *z = y->left;

            	y->left = x, x->right = z, x->update_height();

            	return y->update_height();
        	}

        	node* rotate_right(const T x)
        	{
            	if (x < left->key)
                	return rotate_right_aux(this);

            	if (left->key < x)
            	{
                	left = rotate_left_aux(left);

                	return rotate_right_aux(this);
            	}

            	return this;
        	}

        	node* rotate_left(const T x)
        	{
            	if (right->key < x)
                	return rotate_left_aux(this);

            	if (x < right->key)
            	{
                	right = rotate_right_aux(right);

                	return rotate_left_aux(this);
            	}

            	return this;
        	}

        	friend node* insert_key(node* t, const T x)
        	{
            	return t? t->insert(x):new node(x);
        	}

        	node* insert(const T x)
        	{
            	if (x < key)
                	left = insert_key(left,x);
            	else if (key < x)
                	right = insert_key(right,x);
            	else
            	{
                	count++; return this;
            	}

            	update_height(); int balance = Balance();

            	if (balance > 1)
                	return rotate_right(x);

            	if (balance < -1)
                	return rotate_left(x);

            	return this;
        	}

        	template<class OutputIterator>
        	OutputIterator copy_all(OutputIterator result, bool distinct) const
        	{
        		if(left)
        			result = left->copy_all(result,distinct);

        		*result++ = key;

        		if(not distinct)
                    for(size_t j = 1; j < count;++j)
                        *result++ = key;

        		if(right)
        			result = right->copy_all(result,distinct);

                return result;
        	}

			friend std::ostream& operator << (std::ostream& out, const node* t)
			{
				if (t->left)
					out << t->left << ' ';

				out << t->key;

				for(int i = 1, n = t->count; i < n; i++)
					out << ' ' << t->key;

				if (t->right)
					out << ' ' << t->right;

				return out;
			}

    	} *root;

	public:
    	multiset() : root(nullptr) {}

    	void insert(T key)
    	{
        	root = insert_key(root,key);
    	}

		template<class InputIterator>
    	void insert(InputIterator first, InputIterator last)
    	{
    	    while(first != last)
                root = insert_key(root,*first++);
    	}
    	
    	template<class OutputIterator>
    	OutputIterator copy_all(OutputIterator result, bool distinct = false) const
    	{
    		if(root)
    			result = root->copy_all(result,distinct);

            return result;
    	}

    	friend std::ostream& operator << (std::ostream& out, const multiset& t)
    	{
    		if(t.root)
    			out << t.root;

    		return out;
    	}
	};
}

namespace timer
{
    typedef std::chrono::high_resolution_clock     Clock_t;
    typedef std::chrono::time_point<Clock_t>        Time_t;
    typedef std::chrono::milliseconds         Time_scale_t;

    static Time_t present;

    inline void reset()
    {
        present = Clock_t::now();
    }

    inline size_t elapsed_time()
    {
        auto past = present;

        reset();

        return std::chrono::duration_cast<Time_scale_t>(present-past).count();
    }
}

using namespace std;

inline void time_info(const string& info, size_t t)
{
	cout << "time(" << info << ") = " << t << " msec" << endl;
}


const int m = 1e5, n = 2e6, N = 1e5; mt19937_64 Random;

vector<int> a1(n), x(n), a2(n), q(m), ans(m);

AVL::multiset<int> b1; multiset<int> b2;

int main()
{
	ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	
	for_each(q.begin(),q.end(),[](int &key){key = Random()%N;}),
    for_each(x.begin(),x.end(),[](int &key){key = 1+Random()%N;}),
    timer::reset(),
    b1.insert(x.begin(),x.end());

	const auto u_search = [](int a)
	{
		return upper_bound(a1.begin(),a1.end(),a)-a1.begin();
	};

	auto t_insert1 = timer::elapsed_time();

	b2.insert(x.begin(),x.end());

	auto t_insert2 = timer::elapsed_time();

    b1.copy_all(a1.begin());

    auto t_copy1 = timer::elapsed_time();

    copy(b2.begin(),b2.end(),a1.begin());

    auto t_copy2 = timer::elapsed_time();

    transform(q.begin(),q.end(),ans.begin(),u_search);

    auto t_upper_bound = timer::elapsed_time();

    cout << "Performance comparison using " << n << " items" << endl,
    time_info("insert-AVL-multiset",t_insert1),
    time_info("insert-std-multiset",t_insert2),
    time_info("copy-AVL-multiset",t_copy1),
    time_info("copy-std-multiset",t_copy2),
    cout << "Performance of processing " << m << " queries" << endl,
    time_info("upper-bound",t_upper_bound);
}