class cart_tree {
  typedef struct _Node {
    int x, y;
    ll sum;
    int cnt;
    _Node *l, *r;

    _Node(int _x) : x(_x), y(rand()), sum(_x), cnt(1), l(0), r(0) {}
    ~_Node() {
      if (l) delete l;
      if (r) delete r;
    }
    void recalc() {
      sum = x; cnt = 1;
      if (l) sum += l->sum, cnt += l->cnt;
      if (r) sum += r->sum, cnt += r->cnt;
    }
  } *Node;

  Node merge(Node l, Node r) {
    if (!l) return r;
    if (!r) return l;

    if (l->y < r->y) {
      l->r = merge(l->r, r);
      return l->recalc(), l;
    } else {
      r->l = merge(l, r->l);
      return r->recalc(), r;
    }
  }
  void split(Node v, int key, Node &l, Node &r) {
    l = r = 0;
    if (!v) return;

    Node tmp;
    if (v->x <= key) {
      split(v->r, key, tmp, r);
      v->r = tmp;
      l = v;
    } else {
      split(v->l, key, l, tmp);
      v->l = tmp;
      r = v;
    }
    v->recalc();
  }

  void print(Node v) {
    if (!v) { eoprintf("null\n"); return; }
    eoprintf("x=%d, sum=%lld, cnt=%d\n", v->x, v->sum, v->cnt);
    eoff += 2;
    print(v->l);
    print(v->r);
    eoff -= 2;
  }

  Node root;

  public:
  cart_tree() : root(0){}

  void insert(int x) {
    Node l, r;
    split(root, x, l, r);
    root = merge(merge(l, new _Node(x)), r);
  }
  pair<ll, int> getLeqThan(int x) {
    Node l, r;
    split(root, x, l, r);
    pair<ll, int> res(0, 0);
    if (l) res = mp(l->sum, l->cnt);
    root = merge(l, r);
    return res;
  }
};