template <class T>
struct treap {
private:
	struct node {
		T key;
		unsigned long long priority;
		unsigned size;
		node *left, *right;
	};
	struct xorshift {
		unsigned long long x,y,z,w;
		xorshift(): x(1234567891011121314), y(91734892562378), z(77777777777777), w(986732789462378) {}
		unsigned long long next() {
			unsigned long long t=x^(x<<11);
			x=y;y=z;z=w;
			return w=w^(w>>19)^t^(t>>8);
		}
	};
	typedef node *node_ptr;
	node_ptr root;
	xorshift rng;
	unsigned long long next() {
		return rng.next();
	}
	node_ptr new_node(T key) {
		node_ptr res=(node_ptr)malloc(sizeof(node));
		res->key=key;
		res->priority=next();
		res->size=1;
		res->left=NULL;
		res->right=NULL;
		return res;
	}
	unsigned size(node_ptr &root) {
		if(root==NULL) return 0;
		else return root->size;
	}
	void update_size(node_ptr &root) {
		if(root!=NULL) root->size=1+size(root->left)+size(root->right);
	}
	node_ptr right_rotation(node_ptr x) {
		node_ptr y=x->left,t2=y->right;
		x->left=t2;
		y->right=x;
		update_size(x);
		update_size(y);
		return y;
	}
	node_ptr left_rotation(node_ptr y) {
		node_ptr x=y->right,t2=x->left;
		y->right=t2;
		x->left=y;
		update_size(y);
		update_size(x);
		return x;
	}
	node_ptr insert(node_ptr root, T key) {
		if(root==NULL) {
			return new_node(key);
		}
		else if(key<root->key) {
			root->left=insert(root->left,key);
			if(root->left->priority>root->priority) root=right_rotation(root);
		}
		else {
			root->right=insert(root->right,key);
			if(root->right->priority>root->priority) root=left_rotation(root);
		}
		update_size(root);
		return root;
	}
	node_ptr remove_it(node_ptr root) {
		if(root->left==NULL && root->right==NULL) {
			return NULL;
		}
		if(root->left==NULL) {
			root=left_rotation(root);
			root->left=remove_it(root->left);
			update_size(root);
			return root;
		}
		if(root->right==NULL) {
			root=right_rotation(root);
			root->right=remove_it(root->right);
			update_size(root);
			return root;
		}
		if(root->left->priority>root->right->priority) {
			root=right_rotation(root);
			root->right=remove_it(root->right);
		}
		else {
			root=left_rotation(root);
			root->left=remove_it(root->left);
		}
		update_size(root);
		return root;
	}
	node_ptr erase(node_ptr root, T key) {
		if(key<root->key) {
			root->left=erase(root->left,key);
		}
		else if(key>root->key) {
			root->right=erase(root->right,key);
		}
		else {
			root=remove_it(root);
		}
		update_size(root);
		return root;
	}
	unsigned count_less(node_ptr root, T key) {
		if(root==NULL) return 0;
		else if(key<root->key) return count_less(root->left,key);
		else if(key==root->key) return size(root->left);
		else return 1+size(root->left)+count_less(root->right,key);
	}
	T kth(node_ptr root, unsigned k) {
		if(1+size(root->left)==k) return root->key;
		else if(k<=size(root->left)) return kth(root->left,k);
		else return kth(root->right,k-1-size(root->left));
	}
	bool find(node_ptr root, T key) {
		if(root==NULL) return false;
		else if(key<root->key) return find(root->left,key);
		else if(key>root->key) return find(root->right,key);
		else return true;
	}
public:
	treap(): root(NULL) {}
	void clear() {
		root=NULL;
		rng=xorshift();
	}
	unsigned size() {
		return size(root);
	}
	bool empty() {
		return (size()==0);
	}
	bool find(T key) {
		return find(root,key);
	}
	void insert(T key) {
		if(find(key)==false) root=insert(root,key);
	}
	void erase(T key) {
		if(find(key)==true) root=erase(root,key);
	}
	T kth(unsigned k) {
		return kth(root,k);
	}
	unsigned count_less(T key) {
		return count_less(root,key);
	}	
};