#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds;

template<class Node_CItr, class Node_Itr, class Cmp_Fn, class _Alloc>
struct order_statistics_frequency_list_update {
  typedef size_t metadata_type;
  void operator()(Node_Itr it, Node_CItr end_it) {
    cout<<(*it)->first<<"**"<<(*it)->second<<endl;
    metadata_type x = (*it)->second;
    const auto left_child = it.get_l_child();
    const auto right_child = it.get_r_child();
    if (left_child != end_it) {
      x += left_child.get_metadata();
    } 
    if (right_child != end_it) {
      x += right_child.get_metadata();
    }
    const_cast<metadata_type&>(it.get_metadata()) = x;
  }
  size_t order_of_key(int64_t key) {
    size_t order = 0;
    auto it = node_begin();
    const auto end = node_end();
    while (it != end) {
      const auto left_child = it.get_l_child();
      const auto right_child = it.get_r_child();
      if (Cmp_Fn()(key, (*it)->first)) {
        it = left_child;
      } else {
        if (left_child != end) order += left_child.get_metadata();
        if (key == (*it)->first) return order;
        order += (*it)->second;
        it = right_child;
      }
    }
    return order;
  }
  metadata_type find_by_order(size_t order) {
    auto it = node_begin();
    const auto end = node_end();
    while (it != end) {
      const auto left_child = it.get_l_child();
      const auto right_child = it.get_r_child();
      size_t lchild_size = (left_child == end)? 0 : left_child.get_metadata();
      if (order >= lchild_size) {
        order -= lchild_size;
        if (order >= (*it)->second) {
          order -= (*it)->second;
          it = right_child;
        } else return (*it)->first;
      } else {
        it = left_child;
      }
    }
    return (*it)->first;
  }
  virtual Node_CItr node_begin() const = 0;
  virtual Node_CItr node_end() const = 0;
};


typedef tree<
  int64_t, 
  size_t, 
  less<int64_t>, 
  rb_tree_tag, 
  order_statistics_frequency_list_update
> ordered_multiset;