#ifndef skeleta
#include "orderedset.h"
#endif

#include <bits/stdc++.h>

using namespace std;

#define T long long

const int BUCKETS = 40;
const long long B = 1000000000000000000/BUCKETS;


struct node {
  T key;
  unsigned long long priority;
  unsigned size;
  node *left, *right;
};

node node_buff[1000007];
int buff_pos;

struct treap {
  private:
        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));
      node_ptr res=&node_buff[buff_pos++];
      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);
    }
};

treap t[BUCKETS + 4];

void add_number(long long x) {
  t[x/B].insert(x);
}

void remove_number(long long x) {
  t[x/B].erase(x);
}

long long kth_number(int k) {
  for(int i=0;i<BUCKETS;i++) {
    if(t[i].size()>=k) {
      return t[i].kth(k);
    }
    k-=t[i].size();
  }
}

#ifdef skeleta
int main() {

}
#endif